Medium Bisect Left/Right Binary Search
In plain English: Find where a number first and last appears in a sorted list that may have duplicates.
Two binary searches: bisect-left finds the first occurrence, bisect-right minus one finds the last — both run in O(log n).
Prompt
Given a sorted array with duplicates and a target, find the first and last index of the target. Return [-1, -1] if not found.
Try to write it from scratch before scrolling down.
Solution
def search_range(a, target):
def bisect_left(a, t):
lo, hi = 0, len(a)
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < t:
lo = mid + 1
else:
hi = mid
return lo
def bisect_right(a, t):
lo, hi = 0, len(a)
while lo < hi:
mid = (lo + hi) // 2
if a[mid] <= t:
lo = mid + 1
else:
hi = mid
return lo
left = bisect_left(a, target)
right = bisect_right(a, target) - 1
if left <= right and left < len(a) and a[left] == target:
return [left, right]
return [-1, -1]
# Test: search_range([5,7,7,8,8,10], 8) == [3, 4]
# Test: search_range([5,7,7,8,8,10], 6) == [-1, -1]