Start learning free

LESSON 155 OF 414 · LOOPING OVER ARRAY INDICES

Linear Search in Rust: O(n) Time and O(1) Space

Practice Read the full explanation

Given an array of integers nums, return the index of a given value.

If the value doesn't exist, return -1.

Example 1:

Input: nums = [1, 2, 4, 5], value = 4
Output: 2
Explanation: nums[2] is 4

Note:

Your algorithm should run in O(n) time and use O(1) space.


Hints:

We should try out each element in nums until we find one equal to value and return its index. How can we achieve this?

With a for loop, of course! We can use a variable num to iterate through the elements and an if statement to check if num is equal to value. If it is, we have found the solution! But...
This is how we look for value in nums, but there's a problem. The problem asks us to return the index of that element, and by iterating like this we only know the value of the current element, not its index. How can we fix this?

We should use another method of iterating through an array: by indices! Let's use an index variable i to go through every index between 0 and nums.len() - 1.
For each index i, the index is i and the value is the element of nums at that index. If that element is equal to value, we return i.
What if we don't have any element equal to value? Where should we return -1?

After the loop, outside of it, we return -1.
If we reach that line, this means the for loop terminated naturally without returning any index. If we had returned an index, we wouldn't even be executing this line of code as the program would have finished.

We have a for loop that performs exactly n iterations (where n is the length of nums), thus the Time Complexity is O(n).
The only extra space we use is the iterator variable i inside the loop, thus the Extra Space used is O(1).

Video Solution:

STEP 1 OF 3
    Ctrl + Enter to check

    RUST · LOOPING OVER ARRAY INDICES

    Linear Search in Rust, explained

    Problem overview

    The function find receives a vector of integers, nums, and an integer value. It returns the index where value sits in nums, or -1 when the value isn't there. The statement sets a budget of O(n) time and O(1) extra space.

    For nums = [1, 2, 4, 5] and value = 4, the answer is 2, because nums[2] is 4. For value = 3, nothing matches, so the answer is -1.

    Approach: try every position in order

    The vector is not promised to be sorted, so the only way to know a value is absent is to look at every element. Linear search does exactly that: it starts at index 0 and moves right, one element at a time, and stops at the first match.

    The answer is a position, not a value. A loop that hands you the elements, such as for num in &nums, tells you what each element is but not where it is. So the loop here runs over indices, and the element is read with nums[i].

    The value -1 works as the "not found" marker because no real index is negative. Returning it after the loop is safe: the line is reached only when no iteration found a match and returned early.

    Step by step

    1. Loop over the indices. Use for i in 0..nums.len(). The range stops before len(), so i takes every valid index and nothing beyond.
    2. Compare and return. If nums[i] == value, the search is over. Return i as i32 immediately. The early return means a value that appears several times gives its first index.
    3. Return -1 after the loop. The loop ran to the end without finding the value, so report that it is missing.

    The solution in Rust

    impl Solution {
    fn find(nums: Vec<i32>, value: i32) -> i32 {
        for i in 0..nums.len() {
            if nums[i] == value {
                return i as i32;
            }
        }
        return -1;
    }
}

    The Rust details worth a closer look:

    • usize versus i32. 0..nums.len() is a range of usize, the type Rust uses for indices, so i is a usize. The function returns an i32, and Rust never converts between integer types silently. Writing return i; is a compile error ("expected i32, found usize"). The cast i as i32 does the conversion.
    • Casts can truncate. as doesn't check the value. A usize above i32::MAX would wrap to a wrong number. For a vector that can reach billions of elements that matters; for this lesson's inputs it doesn't.
    • Why -1 is possible. The return type is signed, which is what allows a negative marker. A usize return type couldn't hold it, and that is one reason the function returns i32.
    • Comparing integers. nums[i] == value compares two i32 values. Indexing a vector gives the element itself (copied here, since i32 is Copy), so no dereferencing is needed.
    • Idiomatic alternative. The standard library has nums.iter().position(|&x| x == value), which returns an Option<usize>: Some(index) or None. Writing the loop yourself first shows what position does.

    Complexity

    Time: O(n). In the worst case, a missing value or one at the very end, the loop checks all n elements, each in constant time. In the best case, the first element matches and the loop does one check. The bound that holds for every input is O(n).

    Space: O(1). The loop keeps one index variable, regardless of how long the vector is. The vector itself is the input and isn't counted as extra space.

    Edge cases and common mistakes

    • Value not present. [1, 2, 4, 5] with value 3 returns -1.
    • Empty vector. The range 0..0 is empty, the loop body never runs, and the function returns -1.
    • Duplicates. [7, 7, 7] with value 7 returns 0. Because the function returns at the first match, it never sees the later ones.
    • Returning inside the wrong place. Putting return -1 in an else branch inside the loop makes the function give up after the first element. The "not found" answer belongs after the loop.
    • Returning the value instead of the index. return nums[i] compiles but answers a different question.
    • Forgetting the cast. return i; fails to compile because i is a usize.
    • Mixing up the result of a missing value with index 0. The answer for an absent value is -1, not 0, since 0 is a real index.

    Testing

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