The problem
In a sorted list, find the first and last position of a target value, or [−1, −1].
Input: [5, 7, 7, 8, 8, 8, 8, 10, 12], target = 8 Output: [3, 6]
Picture it
Picture a library shelf with several copies of the same book in a row. Run binary search twice: once leaning left to find the first copy, once leaning right to find the last copy.
Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.
The key idea
Two binary searches (lower bound and upper bound). O(log n).
Python solution
def search_range(a, t):
def bound(first):
lo, hi, ans = 0, len(a) - 1, -1
while lo <= hi:
mid = (lo + hi) // 2
if a[mid] == t:
ans = mid
if first: hi = mid - 1 # keep looking left
else: lo = mid + 1 # keep looking right
elif a[mid] < t:
lo = mid + 1
else:
hi = mid - 1
return ans
return [bound(True), bound(False)]In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.