Start learning free

LESSON 286 OF 414 · DIVIDE AND CONQUER

Binary Search in Rust: O(log n) Recursive Version with Slices

Practice Recursive Read the full explanation

Implement a recursive Binary Search algorithm that given a sorted array of integers nums, finds and returns the index of a given value.

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

Example 1:

Input: nums = [1, 2, 4, 5], value = 4
Output: 2
Explanation: the element at index 2 is 4

Note:

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

Hints:

Since our subproblems reduce to searching the value in a subarray, we will write a recursive helper function which takes nums, the bounds left and right and value, looks for value in the part of nums between indexes left and right (both included) and returns its index or -1 if not found.

Inside the function, we should compute the middle index mid and compare the element at mid to value. What should we do if:
  • the element at mid is equal to value?
  • the element at mid is less than value?
  • the element at mid is greater than value?

  • If the element at mid is equal to value, then we found our solution and we should return mid
  • If the element at mid is less than value, we should continue the search between indexes mid + 1 and right, i.e. return the result of the recursive call on that range
  • If the element at mid is greater than value, we should continue the search between indexes left and mid - 1, i.e. return the result of the recursive call on that range
When should the function return -1 tho?

At the start of the function, we should treat the base case: left > right. This means we reduced the searching area to an empty subarray, so there is no solution and we should return -1
STEP 1 OF 7
    Ctrl + Enter to check

    RUST · DIVIDE AND CONQUER

    Binary Search in Rust, explained

    Problem overview

    The function find receives a sorted vector of integers, nums, and a number value. It returns the index where value sits, or -1 when it isn't there. The lesson asks for a recursive solution that runs in O(log n) time and uses O(log n) extra space.

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

    Approach: discard half of the array each time

    Checking every element is O(n). Because the vector is sorted, one comparison can rule out half of what is left. Look at the middle element:

    • If it equals value, return its index.
    • If it is smaller than value, everything to its left is smaller too, so the answer can only be in the upper half.
    • If it is larger, the answer can only be in the lower half.

    The recursion needs to say which part of the vector it is searching. A helper takes the whole slice plus two bounds, left and right, both inclusive, and searches only nums[left..=right]. Passing bounds means no copies of the data: each call works on the same slice with a smaller range. When left moves past right, the range is empty and the value isn't present.

    Each call halves the range, so a vector of a million elements needs about 20 calls. The calls stack up one inside another, which is where the O(log n) space comes from.

    Step by step

    1. Start from find. Compute the last index as an i32, nums.len() as i32 - 1, and call the helper through Self:: with &nums, the bounds 0 and right, and value. The & borrows the vector so the helper doesn't take ownership.
    2. Declare the helper above find. It takes a borrowed slice &[i32], the bounds left and right, and value, and returns an i32.
    3. Base case. If left > right, the range is empty. Return -1.
    4. Find the middle, mid = (left + right) / 2. Integer division rounds down, so mid is always inside the range.
    5. Found it. If nums[mid as usize] equals value, return mid. Slices are indexed with usize, so the i32 index needs an explicit cast.
    6. Element too small. Recurse on the upper half, from mid + 1 to right. This call is the value of the branch, with no return.
    7. Element too large. In the else branch, recurse on left to mid - 1. Using mid - 1 and mid + 1 instead of mid matters: mid has just been checked, and keeping it could make the range stop shrinking.

    The solution in Rust

    impl Solution {
    fn binary_search_helper(nums: &[i32], left: i32, right: i32, value: i32) -> i32 {
        if left > right {
            return -1;
        }
        let mid = (left + right) / 2;
        if nums[mid as usize] == value {
            return mid;
        }
        if nums[mid as usize] < value {
            Self::binary_search_helper(nums, mid + 1, right, value)
        } else {
            Self::binary_search_helper(nums, left, mid - 1, value)
        }
    }

    fn find(nums: Vec<i32>, value: i32) -> i32 {
        let right = nums.len() as i32 - 1;
        Self::binary_search_helper(&nums, 0, right, value)
    }
}

    The Rust details worth a closer look:

    • Why i32 bounds. The bounds are signed because right becomes -1 for an empty vector, and mid - 1 can reach -1 when the value is smaller than everything. A usize can't hold -1: subtracting 1 from a usize that is 0 panics in a debug build and wraps to a huge number in an optimized one.
    • Precedence of as. In nums.len() as i32 - 1, the cast binds tighter than the subtraction, so the length is converted first and then reduced by one. For an empty vector that gives -1, and the helper returns -1 at once without touching any element.
    • Passing &nums. nums is a Vec<i32>, and the helper wants a &[i32]. Rust converts a reference to a vector into a slice automatically, so the call compiles and no data is copied.
    • if/else as an expression. Both branches end without a semicolon and have type i32, so the whole if/else is the value of the function. The two branches must have the same type.
    • Casting to index. mid as usize is safe here because mid is never negative once the base case has passed: left <= right and left starts at 0 and only grows.
    • Sum overflow. left + right would overflow an i32 only for a vector with more than a billion elements. A vector that large already needs over 4 GB for the numbers alone. The safer form left + (right - left) / 2 avoids the issue.

    Complexity

    Time: O(log n). Each call does a constant amount of work and then makes at most one recursive call on at most half the range. Halving n repeatedly reaches an empty range after about log n steps.

    Space: O(log n). Nothing is copied, but every call that hasn't returned yet occupies a stack frame. The deepest chain is about log n calls long. An iterative version with a loop would need O(1) space.

    Edge cases and common mistakes

    • Empty vector. nums = [] gives -1, because the first call has left = 0 and right = -1.
    • One element. With nums = [7] and value = 7, the range is one element, mid is 0 and the answer is 0.
    • Value at either end. In [1, 2, 4, 5], searching for 1 gives 0 and searching for 5 gives 3.
    • Value missing. Searching for 3 in [1, 2, 4, 5] narrows the range until left passes right, and the result is -1.
    • Duplicates. In [1, 2, 2, 2, 3], searching for 2 returns 2, the middle copy. The function returns the index of some match, not necessarily the first.
    • Recursing on mid instead of mid + 1 or mid - 1. The range can stop shrinking, and the calls never end.
    • Missing base case. Without the left > right check, a missing value leads to an out-of-bounds index and a panic, or to infinite recursion.

    Testing

    • nums = [1, 2, 4, 5], value = 4 gives 2.
    • nums = [1, 2, 4, 5], value = 1 gives 0.
    • nums = [1, 2, 4, 5], value = 3 gives -1.
    • nums = [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