Start learning free

LESSON 276 OF 414 · BINARY SEARCH

Lower Bound in Rust: O(log n) Binary Search

Practice O(log n) Read the full explanation

Given a sorted array of integers nums, find the smallest index where we can place a given value such that the array remains sorted

Example 1:

Input: nums = [1, 2, 3, 5, 7], value = 4
Output: 3
Explanation: Placing the value 4 at index 3 we obtain nums = [1, 2, 3, 4, 5, 7]

Example 2:

Input: nums = [1, 2, 3], value = 2
Output: 1
Explanation: Placing the value 2 at index 1 we obtain nums = [1, 2, 2, 3]

Note:

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


STEP 1 OF 6
    Ctrl + Enter to check

    RUST · BINARY SEARCH

    Lower Bound in Rust, explained

    Problem overview

    The function lower_bound takes a sorted vector nums and a value. It returns the smallest index at which value could be inserted so that the vector stays sorted. Equivalently, it returns the index of the first element that is not less than value.

    For nums = [1, 2, 3, 5, 7] and value = 4 the answer is 3: inserting 4 at index 3 gives [1, 2, 3, 4, 5, 7]. For nums = [1, 2, 3] and value = 2 the answer is 1, the index of the existing 2, since inserting there still keeps the order. If every element is smaller than value, the answer is the length of the vector, one past the last index.

    The statement asks for O(log n) time and O(1) extra space.

    Approach: binary search for the boundary

    A linear scan would stop at the first element that is at least value, which costs O(n). Because the vector is sorted, the elements split into two blocks: first the ones smaller than value, then the ones that are not. The answer is the index where the second block starts, and binary search can find a boundary like that in O(log n).

    Look at the middle element of the current range:

    • if it is smaller than value, it and everything to its left belong to the first block, so the boundary is further right;
    • otherwise it belongs to the second block, so the boundary is at middle or to its left.

    Unlike the plain binary search for a value, there is no early exit on equality: even when the middle equals value, an earlier copy might exist, so the search keeps going to the left. When the range is empty, left sits exactly on the boundary.

    On [1, 2, 3, 5, 7] with value = 4: the range is indexes 0 to 4 and the middle is index 2, holding 3, which is smaller, so left becomes 3. The range 3 to 4 has middle 3, holding 5, which is not smaller, so right becomes 2. Now left is 3 and right is 2, the loop ends, and 3 is returned.

    Duplicates show why the search must not stop on equality. On [1, 2, 2, 3] with value = 2, the first middle is index 1, which holds 2. That element is not smaller than value, so right becomes 0. The next middle is index 0, holding 1, which is smaller, so left becomes 1. The loop ends with left = 1, the first 2. A search that returned at the first match would be wrong on [2, 2, 2, 2]: its first middle is index 1, but the answer is 0.

    The same function also answers "is the value present?": it is present exactly when the returned index is below nums.len() and the element at that index equals value.

    Step by step

    1. Set the bounds. left is 0i32, and right is nums.len() as i32 - 1. Both are signed because right becomes -1 when every element is at least value, and an unsigned type can't hold that.
    2. Loop while left <= right. The range is inclusive, so one remaining element still gets examined.
    3. Compute middle as (left + right) / 2. Integer division discards the fraction, so it is always a valid index.
    4. If nums[middle as usize] < value, no index up to middle can be the answer, so left = middle + 1.
    5. Otherwise middle might be the answer, but nothing to its right can be better, so right = middle - 1.
    6. Return left. When the loop ends, right is left - 1: everything before left is smaller than value, and everything from left on is at least value.

    The solution in Rust

    impl Solution {
    fn lower_bound(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) / 2;
            if nums[middle as usize] < value {
                left = middle + 1;
            } else {
                right = middle - 1;
            }
        }
        left
    }
}

    Rust details to note:

    • Signed bounds. With right as a usize, an empty vector would make nums.len() - 1 wrap around in an optimized build and panic in a debug build. Casting the length to i32 first turns it into a plain -1.
    • Indexing needs usize. nums[middle as usize] is the only place where the cast is needed. Rust doesn't convert between integer types on its own.
    • The midpoint. (left + right) / 2 adds two indexes. A vector's length is far below the point where that could overflow an i32, which is why the lesson uses the simple form. left + (right - left) / 2 is the form that stays safe even for bounds near the top of the i32 range.
    • The tail expression. The function ends with left, with no semicolon and no return.

    Complexity

    Time: O(log n). Each pass through the loop discards at least half of the range, so there are about log₂ n passes, each doing one comparison.

    Space: O(1). Only left, right and middle are kept.

    Edge cases and common mistakes

    • Empty vector. right is -1, the loop never runs, and left, 0, is returned.
    • Value smaller than everything. [1, 2, 3] with 0 returns 0.
    • Value larger than everything. [1, 2, 3] with 10 returns 3, the length. That index doesn't exist in the vector, so use it only as an insertion position and never read nums[result] without checking.
    • Duplicates. [2, 2, 2, 2] with 2 returns 0, the first copy, and [1, 2, 2, 3] with 3 returns 3. Using <= in the comparison would return the position after the last equal element instead.
    • Returning on equality. Stopping as soon as the middle equals value may return a later duplicate instead of the first.
    • Using left < right in the loop condition. With this inclusive-bounds version, the last remaining element would never be examined.

    Testing

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