LESSON 277 OF 414 · BINARY SEARCH

Number of Occurrences in Rust: O(log n) with Two Lower Bounds

Practice O(log n) Read the full explanation

Given a sorted array of integers nums, count the number of occurrences of a given value.

Example:

Input: nums = [1, 2, 2, 2, 4, 5], value = 2
Output: 3
Explanation: the value 2 appears 3 times in the array

Note:

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

Hints:

If value exists in nums, it will occur in a subarray of consecutive elements. If we manage to find this subarray, we'll also know the number of occurrences of value.

This subarray is determined by the first and last indices where value occurs in nums. How would you find the first occurrence in O(log n) time?

We can find the first occurrence using an algorithm we have already studied: Lower Bound.
Can you write a similar binary search algorithm for finding the last occurrence of value in nums?

We will implement a binary search and use a variable ans to store the best answer found so far, just like we did in Lower Bound. The only difference is how we handle the cases for each mid index. What should we do if:

the element at index mid is greater than value?
the element at index mid is less than or equal to value?

If the element at index mid is greater than value, we should continue the search in the part of nums from left to mid - 1, e.g. set right to mid - 1
If the element at index mid is less than or equal to value, we should set ans to mid and continue the search in the part of nums from mid + 1 to right, e.g. set left to mid + 1

STEP 1 OF 10

Guided

Ctrl + Enter to check

Number Of Occurrences in Rust, explained

Problem overview

The function count receives a sorted vector nums and a target, and returns how many times target appears. For nums = [1, 2, 2, 2, 4, 5] and target = 2 the answer is 3.

The statement asks for O(log n) time and O(1) extra space, so scanning the whole vector and counting (O(n)) is too slow.

Approach: the range of equal values is bounded by two lower bounds

Because the vector is sorted, all copies of target sit next to each other. If you know where that block starts and where it ends, the count is the difference of the two positions.

Both positions come from the same tool, the lower bound: the index of the first element that is not less than a given value. Then:

the lower bound of target is the index where the block of target starts;
the lower bound of target + 1 is the index of the first element greater than target, since the elements are integers. That is one past the end of the block.

The number of occurrences is the second index minus the first. If target is missing, both searches land on the same index and the difference is 0, with no special case.

On [1, 2, 2, 2, 4, 5] with target = 2: the lower bound of 2 is index 1, and the lower bound of 3 is index 4 (the element 4 is the first one not below 3). The answer is 4 - 1 = 3.

For a missing value, take target = 3 in the same vector. The lower bound of 3 is index 4, because 4 is the first element not below 3. The lower bound of 4 is also index 4. The difference is 0, which is correct: nothing sits between the two positions.

Step by step

The lesson builds count first, assuming the helper exists, and then writes the helper.

Find the start. lo is Self::lower_bound_idx(&nums, target). The &nums lends the vector as a slice, so nums isn't moved into the call.
Find the end. hi is the same call with target + 1.
Return the difference (hi - lo) as i32. The indexes are usize and the function returns i32, and the subtraction is in parentheses because as binds tighter than -.
Declare the helper lower_bound_idx(nums: &[i32], value: i32) -> usize.
Use a half-open range. left is 0usize and right is nums.len(), one past the last index, so the range is [left, right). This avoids the -1 that an inclusive upper bound would need for an empty vector, which a usize can't hold.
Loop while left < right. A half-open range is empty once the bounds meet.
Compute mid as left + (right - left) / 2. It always lies inside the range.
If nums[mid] < value, the answer is to the right: left = mid + 1.
Otherwise mid could itself be the answer, so it must stay in the range: right = mid. With a half-open range, mid - 1 would be wrong, because it would exclude mid.
Return left, the first index whose element is at least value, or nums.len() if there is none.

The solution in Rust

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

    fn count(nums: Vec<i32>, target: i32) -> i32 {
        let lo = Self::lower_bound_idx(&nums, target);
        let hi = Self::lower_bound_idx(&nums, target + 1);
        (hi - lo) as i32
    }
}

Rust details worth a look:

Slices. The helper takes &[i32], a borrowed view of the elements. Passing &nums, a &Vec<i32>, works because Rust converts it to a slice automatically, and the vector stays usable for the second call.
Associated functions. Neither function takes self, so the helper is called as Self::lower_bound_idx.
Half-open ranges and usize. Since right is never decreased below left, and right - left is only computed inside left < right, the unsigned subtraction can't go below zero.
Casting the result. as converts usize to i32 and truncates silently if the value doesn't fit; vector lengths in this lesson are far below that limit.
Tail expressions. Both functions end without a semicolon, so left and (hi - lo) as i32 are their return values.

Complexity

Time: O(log n). count runs two binary searches, each halving its range every iteration, so it does about 2 log₂ n iterations in total, which is still O(log n).

Space: O(1). The helper keeps three integers and borrows the vector instead of copying it.

Edge cases and common mistakes

Value missing. [1, 2, 2, 2, 4, 5] with 3 returns 0, and with 0 or 9 it also returns 0, because both bounds land on the same index.
Empty vector. Both searches return 0, so the difference is 0.
All elements equal. [3, 3, 3] with 3 returns 3: the start is 0 and the end is the length.
The largest i32. target + 1 overflows when target is i32::MAX. In an optimized build it wraps to i32::MIN, hi becomes 0, and hi - lo wraps as a usize, so count(vec![1, i32::MAX], i32::MAX) returns -1 instead of 1. A debug build would panic. Inputs in the lesson stay clear of this, but a general-purpose version needs a second search that compares with <=.
Subtracting in the wrong order. lo - hi would underflow the usize.
Using right = mid - 1 in the half-open helper. It can drop the answer from the range, and with usize it can underflow when mid is 0.
Counting with a linear scan. It gives correct results but misses the O(log n) goal.

Testing

[1, 2, 2, 2, 4, 5] with 2 gives 3.
[1, 2, 2, 2, 4, 5] with 3 gives 0.
[3, 3, 3] with 3 gives 3.
[] with 9 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