Count occurrences of a number in a sorted array with duplicates | Optimal Binary Search

Given a sorted array, arr[] and a number target, you need to find the number of occurrences of target in arr[]. 

Here’s the [Problem Link] to begin with.

Examples :

Input: arr[] = [1, 1, 2, 2, 2, 2, 3], target = 2
Output: 4
Explanation: target = 2 occurs 4 times in the given array so the output is 4.

Input: arr[] = [1, 1, 2, 2, 2, 2, 3], target = 4
Output: 0
Explanation: target = 4 is not present in the given array so the output is 0.

Input: arr[] = [8, 9, 10, 12, 12, 12], target = 12
Output: 3
Explanation: target = 12 occurs 3 times in the given array so the output is 3.

Constraints:
1 ≤ arr.size() ≤ 10⁶
1 ≤ arr[i] ≤ 10⁶
1 ≤ target ≤ 10⁶

Optimal Solution (Binary-Search Bounds)

Intuition & Approach

1. Lower Bound (lb) – index of the first element ≥ target.
2. Upper Bound (ub) – index of the first element > target.
3. The number of occurrences is simply ub – lb (length of the closed range holding target).
4. If the lower-bound element isn’t actually target, then target never appears → count = 0.

Code Implementation

class Solution:
    # ---------- helper: first index with value >= target ----------
    def lower_bound(self, nums, target):
        n = len(nums)
        lb  = -1              # default when target isn't found
        low, high = 0, n - 1

        while low <= high:
            mid = (low + high) // 2
            if nums[mid] >= target:
                lb  = mid          # potential first position
                high = mid - 1     # keep searching left half
            else:                  # nums[mid] < target
                low = mid + 1
        return lb

    # ---------- helper: first index with value > target ----------
    def upper_bound(self, nums, target):
        n = len(nums)
        ub  = n               # default when all elements <= target
        low, high = 0, n - 1

        while low <= high:
            mid = (low + high) // 2
            if nums[mid] > target:
                ub  = mid          # potential upper bound
                high = mid - 1     # look further left
            else:                  # nums[mid] <= target
                low = mid + 1
        return ub

    # ---------- driver: count occurrences of target ----------
    def countFreq(self, arr, target):
        lb = self.lower_bound(arr, target)
        # if target never appears, quick exit
        if lb == -1 or arr[lb] != target:
            return 0

        ub = self.upper_bound(arr, target)
        return ub - lb            # total number of occurrences

Code Explanation

• lower_bound narrows leftward whenever it meets a value ≥ target, ensuring the final lb is the first such index—or -1 if no element is big enough.
• upper_bound is identical except it searches for the first value strictly greater than target, returning n when everything is ≤ target.
• Count logic:
  • If arr[lb] isn’t exactly target, the value doesn’t exist, so return 0.
  • Otherwise, every index from lb up to ub – 1 equals target, so the count is ub – lb.

Dry Run (arr = [1, 2, 2, 2, 3], target = 2)

1. Lower bound
   • Finds index 1 (first 2).
2. Upper bound
   • Finds index 4 (first > 2, which is 3).
3. Count = 4 – 1 = 3.

Time & Space Complexity

• Time: O(log n) – each bound is a binary search.
• Space: O(1) – only a few integer variables.

Conclusion

By combining two small tweaks of binary search, you can count a value’s occurrences in a sorted array in logarithmic time, far faster than a linear scan, especially when the array is large. This pattern is a staple for frequency, range, and boundary problems on ordered data.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.