Start learning free

LESSON 139 OF 414 · LOOPS & CONDITIONALS

Array Contains in Rust: Linear Search with an Early Return

Practice Read the full explanation

Given an array of integers nums and another integer value, check if value occurs in nums.

If the value occurs in nums, return true; otherwise return false.


Examples:

contains([1, 2, 4, 5], 4) -> true

contains([-1, 2, -4, 0, 10], 7) -> false

Note:

Do not use builtin functions such as contains(), it would defy the purpose of the challenge. Write the whole code yourself.

STEP 1 OF 3
    Ctrl + Enter to check

    RUST · LOOPS & CONDITIONALS

    Array Contains in Rust, explained

    Problem overview

    The function contains receives a vector of integers, nums, and an integer value. It returns true if value appears anywhere in the vector, and false otherwise. The lesson asks you to write the search yourself instead of using a built-in method.

    For nums = [1, 2, 4, 5] and value = 4 the answer is true. For nums = [-1, 2, -4, 0, 10] and value = 7 the answer is false.

    Approach: look at each element until you find it

    The vector has no order you can rely on, so the only way to know that a value is absent is to check every element. That is a linear search: walk through the vector from the start, compare each element with value, and stop as soon as one matches.

    The two answers need different timing. A match is a final answer: once value is found, nothing else matters, so the function can return true at once. A mismatch proves nothing about the other elements, so false can only be answered after the loop has seen everything. That's why return true goes inside the loop and return false comes after it.

    Step by step

    1. Loop over &nums with the loop variable n. The & borrows the vector instead of consuming it, and each n is a reference to an element.
    2. Compare with *n == value. The reference must be dereferenced with * before it can be compared with the plain i32 in value.
    3. Return true on a match. The function ends immediately, and the remaining elements are not examined.
    4. Return false after the loop. It is only reached when no element matched.

    The solution in Rust

    impl Solution {
    fn contains(nums: Vec<i32>, value: i32) -> bool {
        for n in &nums {
            if *n == value {
                return true;
            }
        }
        return false;
    }
}

    The Rust details to know:

    • References in a for loop. Iterating over &nums yields &i32 values. Comparing n == value with a &i32 and an i32 is a type error, since Rust has no comparison between a reference and a plain integer. The * reads the number behind the reference.
    • Iterating without &. for n in nums moves the vector into the loop, and n is an i32 itself, so n == value compiles. It works for this function. The borrowed form is the habit that keeps a vector usable after the loop.
    • Early return inside a loop. A return leaves the whole function, not only the loop. The final return false; can be written as just false without the semicolon, since the last expression of a function body is its value. The lesson's explicit return does the same.
    • A missing final return fails to compile. If you delete the last line, the compiler reports mismatched types: the loop evaluates to (), but the function must produce a bool.
    • The built-in. Vectors have a contains method, and it is what you would use in everyday code. Here the loop is the point of the exercise.

    Complexity

    Time: O(n). In the worst case the value is last or missing, and every one of the n elements is compared once. If the value is the first element, the function returns after one comparison.

    Space: O(1). The function stores only a reference to the current element.

    Edge cases and common mistakes

    • Empty vector. The loop does not run, and the function returns false, which is right: nothing can be found in an empty vector.
    • Returning false inside the loop. An else { return false; } next to the match gives up after the first element. For [1, 2, 4, 5] and 4, it would compare 1 with 4 and answer false too early.
    • Duplicates. The function stops at the first match. It doesn't matter how many times the value occurs.
    • Negative numbers and zero. They compare like any other integer: [-1, 2, -4, 0, 10] contains 0 and -4.
    • Forgetting the dereference. Writing n == value in the borrowed loop is rejected by the compiler.

    Testing

    • [1, 2, 4, 5] with 4 gives true.
    • [-1, 2, -4, 0, 10] with 7 gives false.
    • [] with 7 gives false.
    • [7] with 7 gives true.
    Keep going with RustAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free