Start learning free

LESSON 249 OF 347 · BINARY SEARCH

Number of Occurrences in a Sorted Array in C#: 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 occurences of value.

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

We can find the first occurence using an algorithm we have already studied: Lower Bound.
Can you write a similar binary search algorithm for finding the last occurence 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 shoud we do if:
  • a[mid] is greater than value?
  • a[mid] is less than or equal to value?


  • If a[mid] is greater than value, we should continue the search in nums[left...mid - 1], e.g. set right to mid - 1
  • If a[mid] is less than or equal to value, we should set ans to mid and continue the search in nums[mid + 1...right], e.g. set left to mid + 1

STEP 1 OF 10
    Ctrl + Enter to check

    C# · BINARY SEARCH

    Number Of Occurrences in C#, explained

    Problem overview

    The method Count receives a sorted int[] nums and an int value. It returns how many times value appears in nums.

    For nums = [1, 2, 2, 2, 4, 5] and value = 2, the 2 appears three times, so the answer is 3. The statement asks for O(log n) time and O(1) extra space, so counting by looping over the array, which is O(n), is not allowed.

    Approach: where the block of equal values starts and ends

    In a sorted array, equal values are neighbours. All copies of value form one block of consecutive indices, and the count is the length of that block. If you know the index where the block starts and the index just after where it ends, the count is the difference.

    Both positions come from the same tool, the lower bound: the first index whose element is not less than a given number.

    • LowerBound(nums, value) is the first index holding value or something larger. If value is present, this is the start of its block.
    • LowerBound(nums, value + 1) is the first index holding value + 1 or something larger. Since the array holds integers, that means the first index whose element is greater than value, which is just past the block.

    The count is the second result minus the first. When value is absent, both calls land on the same index, and the difference is 0.

    On the example, LowerBound(nums, 2) is 1, because nums[1] is the first 2. LowerBound(nums, 3) is 4, because nums[4] = 4 is the first element that is at least 3. The count is 4 - 1 = 3. Each lower bound is a binary search, so the whole method is two O(log n) searches. The array is never scanned element by element, however long the block of equal values is.

    Step by step

    1. Treat LowerBound as available. It takes the array and a value and returns the lower-bound index, as in the Lower Bound lesson. Declare low as LowerBound(nums, value).
    2. Declare high as LowerBound(nums, value + 1). Every occurrence of value sits at an index from low to high - 1.
    3. Return high - low, the number of indices holding value.
    4. Write the helper above Count: public int LowerBound(int[] nums, int value).
    5. Set the bounds in one statement: left = 0 and right = nums.Length - 1.
    6. Loop while left <= right, so the loop keeps going while the window holds at least one element.
    7. Compute middle as (left + right) / 2. Integer division drops the fraction, so it is a valid index.
    8. If nums[middle] < value, set left = middle + 1. Everything up to middle is too small.
    9. Otherwise set right = middle - 1. The element at middle is at least value, so the lower bound is there or further left.
    10. Return left after the loop. It is the first index whose element is at least value, or nums.Length when there is none.

    The solution in C#

    class Solution {
    public int LowerBound(int[] nums, int value) {
        int left = 0, right = nums.Length- 1;
        while (left <= right) {
            int middle = (left + right) / 2;
            if (nums[middle] < value) {
                left = middle + 1;
            } else {
                right = middle - 1;
            }
        }
        return left;
    }

    public int Count(int[] nums, int value) {
        int low = LowerBound(nums, value);
        int high = LowerBound(nums, value + 1);
        return high - low;
    }
}

    C# details:

    • Methods call each other by name. Both methods belong to Solution, so Count calls LowerBound directly, with no object in front. Their order inside the class does not matter in C#.
    • Why value + 1 works. It relies on int values being whole numbers: there is no integer strictly between value and value + 1. With double values it would not work.
    • Overflow is silent. C# does not check int arithmetic by default. If value is int.MaxValue, then value + 1 wraps around to int.MinValue without any error. See the edge cases below.
    • Reusing a tested helper. The array is never modified, and the helper is a separate method, so the two searches cannot interfere with each other. Writing one correct LowerBound and calling it twice is simpler and safer than writing a second, slightly different search for the last occurrence.

    Complexity

    Time: O(log n). Count runs two binary searches, each halving its window at every step. Two times O(log n) is still O(log n).

    Space: O(1). Only a handful of integers are used.

    Edge cases and common mistakes

    • Value not present. [1, 2, 2, 2, 4, 5] with value 3 gives 0: both lower bounds equal 4. A value larger than every element also gives 0, since both calls return nums.Length.
    • Empty array. Both lower bounds return 0, so the count is 0.
    • Whole array equal. [7, 7, 7] with value 7 gives 3 - 0 = 3.
    • The largest possible value. With value = int.MaxValue, value + 1 wraps to int.MinValue, so high becomes 0. For [1, 2147483647] the method returns 0 - 1 = -1 instead of 1. A solution that must handle every int could compute the upper bound with a separate search that uses <= instead of adding 1. Ordinary test values do not reach this limit.
    • Loop condition. Using left < right skips the last candidate and can return a wrong boundary.
    • Returning right. After the loop right is one less than the answer.
    • Counting with a loop. A scan from the first match works, but with many duplicates it degrades to O(n).

    Testing

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