First And Last Occurrence
Problem
A sorted list may hold a target value many times over. Report the first and last positions it occupies, as a pair, or a pair of -1 values when it is absent. The run of equal values can be long, so walking outwards from a hit is too slow.
Examples
Input: nums = [5, 7, 7, 8, 8, 10], target = 8
Output: (3, 4)Input: nums = [5, 7, 7, 8, 8, 10], target = 6
Output: (-1, -1)
Why: the value is absent, even though it sits inside the rangeInput: nums = [], target = 1
Output: (-1, -1)
Why: edge case, an empty list has no positions at allHints
0 / 3
A plain binary search stops at any matching position, which is the one thing you cannot use here — you need a specific end of the run.
Think of the list as a row of yes-or-no answers to a question such as 'is this value at least the target'. That row is always no followed by yes, which is something binary search can find the border of.
Write one helper that returns the leftmost position where a test becomes true. Call it with 'value is at least the target' to get the first position, and with 'value is greater than the target' to get one past the last. Check that the first position really holds the target before trusting either.
Solution
Binary search is really a border finder: given a test that is false for a prefix and true for the rest, it returns the first true position. Asking for the first value at least the target lands on the start of the run, and asking for the first value strictly greater lands one past its end. One guard is still needed, because both answers exist even when the target does not, so the value at the start position has to be checked. Each search is O(log n) and they run one after the other, so time is O(log n) and space is O(1).
def bounds(nums, target):
def first(pred): # leftmost index where pred is true
lo, hi = 0, len(nums)
while lo < hi:
mid = (lo + hi) // 2
if pred(nums[mid]):
hi = mid # mid may itself be the border
else:
lo = mid + 1
return lo
start = first(lambda v: v >= target)
if start == len(nums) or nums[start] != target:
return (-1, -1) # the border exists, the value does not
return (start, first(lambda v: v > target) - 1)
print(bounds([5, 7, 7, 8, 8, 10], 8)) # -> (3, 4)
print(bounds([5, 7, 7, 8, 8, 10], 6)) # -> (-1, -1)
print(bounds([], 1)) # -> (-1, -1)
print(bounds([2, 2], 2)) # -> (0, 1)Stuck on the idea rather than the code? Binary Search Variants covers it.