Introduction

If an array is sorted, counting how many times a value appears does not require scanning the whole array. The efficient approach is to use binary search to find the first position where the target appears and the first position after the target, then subtract the indexes.

That turns the problem from O(n) into O(log n). The trick is to stop thinking in terms of "count every match" and instead think in terms of "find the boundaries of the matching block."

Find The Left And Right Boundaries

Suppose the sorted array is:

[1, 2, 2, 2, 4, 5]

For target 2, the matching values form one continuous block. If you know:

• the first index where 2 appears
• the first index where a value greater than 2 appears

then the count is simply:

rightBoundary - leftBoundary

Python Example With bisect

Python's standard library already implements this pattern in bisect:

1from bisect import bisect_left, bisect_right
2
3def count_occurrences(values, target):
4    left = bisect_left(values, target)
5    right = bisect_right(values, target)
6    return right - left
7
8print(count_occurrences([1, 2, 2, 2, 4, 5], 2))

bisect_left returns the insertion point on the left side of the target block. bisect_right returns the insertion point on the right side. Their difference is the number of occurrences.

Manual Binary Search Version

If you need to implement it yourself, write two boundary searches rather than one ordinary search:

1def first_ge(values, target):
2    lo, hi = 0, len(values)
3    while lo < hi:
4        mid = (lo + hi) // 2
5        if values[mid] < target:
6            lo = mid + 1
7        else:
8            hi = mid
9    return lo
10
11
12def count_occurrences(values, target):
13    left = first_ge(values, target)
14    right = first_ge(values, target + 1)
15    return right - left

This works well for integer targets because target + 1 is the next possible integer boundary. For more general comparable values, write a dedicated upper-bound search instead.

Why Sorting Changes Everything

In an unsorted array, equal values can appear anywhere, so counting them usually requires checking every element. In a sorted array, all equal values are adjacent. That adjacency is what makes binary search useful here.

This is a recurring pattern in algorithms: once data is ordered, many counting and range queries become boundary-finding problems rather than full scans.

Standard Library Support

If you are working in Python, the bisect module already implements the boundary-search idea directly. In C++ the same pattern appears as lower_bound and upper_bound. Learning the boundary concept once pays off across several languages and standard libraries.

Missing Targets Are Easy To Handle

If the target value does not appear in the array, both boundary searches return the same insertion position and the count becomes zero automatically. That is one reason the boundary-based method is cleaner than trying to scan outward from a single found index.

Common Pitfalls

• Falling back to a full linear scan even though the array is already sorted.
• Using a single binary search that finds only one occurrence instead of the boundaries.
• Forgetting that the answer is right - left, not right - left + 1 when using insertion indexes.
• Assuming the target + 1 shortcut works for all data types instead of only integer-like domains.
• Applying the method to data that is not actually sorted.

Summary

• In a sorted array, occurrences of the same integer form one contiguous block.
• Count them by finding the left and right boundaries with binary search.
• Python's bisect_left and bisect_right make this especially simple.
• The efficient time complexity is O(log n).
• Think in terms of boundary positions, not repeated matches.