Given a sorted (ascending) slice that may contain duplicates and a target, return how many times the target appears. Aim for O(log n) using binary search, not a linear scan.
countInSorted(nums, target)
Input format: nums | target.
[5, 7, 7, 8, 8, 8, 10], target=8 // → 3
[5, 7, 7, 8, 8, 8, 10], target=6 // → 0
[1, 1, 1], target=1 // → 3
The obvious way to count occurrences is to scan the array, or binary-search for one occurrence and walk outward counting neighbors. Both can degrade to looking at every matching element — if the target appears many times, that walk-outward step alone costs as much as a linear scan.
Instead of finding matches directly, find where the run of matching values starts and ends. The first index where a value >= target appears, and the first index where a value >= target + 1 appears — everything between those two indices holds exactly target, nothing more, nothing less, since there's no integer between target and target + 1.
Both boundaries are the same query: "find the leftmost index where a value is >= x" — a lower-bound binary search, since that condition is false-then-true across the sorted array.
A scan-outward approach has a worst case where nearly the whole array is the same value — linear time. Computing both boundaries independently via binary search never depends on how many duplicates exist; each takes time proportional to the array's logarithm regardless of whether the target appears once or a million times.
Turning a "how many" question into a difference of two "where does this boundary start" questions is a powerful way to extend binary search beyond existence checks, whenever the quantity you care about is the width of a contiguous run.
def count_in_sorted(nums, target):
def lower_bound(x):
lo = 0
hi = len(nums) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if nums[mid] >= x:
hi = mid - 1
else:
lo = mid + 1
return lo
return lower_bound(target + 1) - lower_bound(target)
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.