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() ≤ 106
1 ≤ arr[i] ≤ 106
1 ≤ target ≤ 106
Contents:
[show]
Optimal Solution (Binary-Search Bounds)
Intuition & Approach
- Lower Bound (
lb
) – index of the first element≥ target
. - Upper Bound (
ub
) – index of the first element> target
. - The number of occurrences is simply
ub – lb
(length of the closed range holdingtarget
). - If the lower-bound element isn’t actually
target
, thentarget
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
PythonCode Explanation
lower_bound
narrows leftward whenever it meets a value≥ target
, ensuring the finallb
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 thantarget
, returningn
when everything is≤ target
.- Count logic:
- If
arr[lb]
isn’t exactlytarget
, the value doesn’t exist, so return0
. - Otherwise, every index from
lb
up toub – 1
equalstarget
, so the count isub – lb
.
- If
Dry Run (arr = [1, 2, 2, 2, 3]
, target = 2
)
- Lower bound
- Finds index
1
(first2
).
- Finds index
- Upper bound
- Finds index
4
(first> 2
, which is3
).
- Finds index
- 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.