LESSON 275 OF 414 · BINARY SEARCH

Binary Search in Rust: Linear Search vs O(log n)

Lesson O(log n) Read the full explanation

In this video lesson we will learn about the concept of searching, linear searching and more important - Binary Searching:

Problem:

Given a sorted array of integers nums, use Binary Search to find and return 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(1) extra space.

STEP 1 OF 7

Guided

Ctrl + Enter to check

Binary Search in Rust, explained

What searching means

Searching is the task of finding where a value sits in a collection, or learning that it isn't there. In this lesson the collection is a Vec<i32> named nums, the value is value, and the function find returns the index of the value, or -1 when it is missing. For nums = [1, 2, 4, 5] and value = 4 the answer is 2, because nums[2] is 4.

Linear search

With no assumptions about the data, the only option is to look at the elements one by one until you find the value or run out. That is linear search, and in the worst case it checks all n elements, so it takes O(n) time.

Binary search

When the vector is sorted, each comparison can rule out a whole half of what remains. Look at the middle element:

if it equals value, you are done;
if it is smaller, then everything to its left is smaller too, so the value can only be on the right;
if it is bigger, the value can only be on the left.

Repeat on the remaining range. A range of 1,000,000 elements shrinks to a single element after about 20 halvings, so the time is O(log n). The extra space is O(1): the search only keeps two index markers.

Here is nums = [1, 2, 4, 5] with value = 4. The range is indexes 0 to 3, and the middle is index 1, which holds 2. Since 2 is smaller than 4, the range becomes indexes 2 to 3. Its middle is index 2, which holds 4: found, return 2.

The exercise, step by step

Set the bounds. left starts at 0 and right at the last index, nums.len() as i32 - 1. Both are inclusive and both are i32, a choice explained below.
Loop while the range is not empty: while left <= right. With <=, a range holding one element, where left equals right, is still checked.
Compute middle as left + (right - left) / 2. Integer division drops the fraction, so middle is always a valid index in the range.
If the middle element equals value, return middle.
If it is smaller, move left to middle + 1.
Otherwise, move right to middle - 1.
If the loop ends, the value isn't there, so the last expression is -1.

The solution in Rust

impl Solution {
    fn find(nums: Vec<i32>, value: i32) -> i32 {
        let mut left = 0i32;
        let mut right = nums.len() as i32 - 1;
        while left <= right {
            let middle = left + (right - left) / 2;
            if nums[middle as usize] == value {
                return middle;
            } else if nums[middle as usize] < value {
                left = middle + 1;
            } else {
                right = middle - 1;
            }
        }
        -1
    }
}

Rust details that matter here

Why i32 bounds. len() returns a usize, which can't be negative. For an empty vector, right must be -1, and 0usize - 1 would wrap around in an optimized build (and panic in a debug build). Casting the length to i32 first makes the subtraction safe.
Casting to index. Vectors are indexed with usize only, and Rust never converts between integer types silently, so the index is written nums[middle as usize]. The cast is safe here because middle is never negative inside the loop.
The overflow-safe midpoint. (left + right) / 2 adds two indexes, which can overflow i32 for huge ranges: with left = 2000000000 and right = 2100000000 the sum wraps to a negative number in an optimized build, and the midpoint comes out as -97483648. left + (right - left) / 2 gives 2050000000. The difference never overflows.
The tail expression. The final -1 has no semicolon, so it is the function's return value. An early return middle; leaves the function from inside the loop.

Common mistakes

Using left < right. The last remaining element is never checked, so find(vec![7], 7) would wrongly give -1.
Setting left = middle or right = middle. The element at middle has already been ruled out. Keeping it in the range can make the loop run forever, for example when left equals middle.
Running it on an unsorted vector. Binary search's reasoning ("everything to the left is smaller") only holds for sorted data. On unsorted data the result is meaningless.
Duplicates. The function returns the index of some matching element, not necessarily the first. For [1, 2, 2, 2, 3] and value = 2 it returns 2, the middle one.

Testing

[1, 2, 4, 5] with 4 gives 2.
[1, 2, 4, 5] with 3 gives -1.
[1, 2, 4, 5] with 1 gives 0, and with 5 gives 3.
[] with 3 gives -1.

Key takeaways

Binary search needs sorted data and halves the range on every comparison: O(log n) time, O(1) space.
Keep both bounds inclusive, loop while left <= right, and always move past middle.
In Rust, use signed i32 bounds and cast with as usize only at the moment of indexing.

Keep going with RustAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free