Binary Search: Find the First Occurrence in a Sorted Array
One problem, three stages: make it work, make it fast, make it lean. Step through each stage in the visualizer, then run all three on a big input in the benchmark and watch the brute force overheat.
The real-world version
An audit log is sorted by timestamp, and many events share the same second. To replay everything from 09:00:00 you need the first event at that time, not just any event at that time.
The problem
Given a sorted array nums that may contain duplicates and a value x, return the index of the first element equal to x, or -1 if it isn't present.
nums = [1, 3, 3, 5, 5, 5, 8, 9, 12], x = 5 → 3
Stage 1 · Smelt: Make it work
Scan from the left and stop at the first element that is ≥ x. Correct, and it never misses the first duplicate.
def first_index(nums, x):
for i, v in enumerate(nums):
if v == x:
return i
if v > x:
break
return -1Why it's not enough: Ignores that the array is sorted: 10 million log rows means up to 10 million checks per query.
Stage 2 · Hammer: Make it fast
Classic binary search finds an x fast, then walks left to the first one. Here d is how many copies of x there are.
def first_index(nums, x):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == x:
while mid > 0 and nums[mid - 1] == x:
mid -= 1 # linear walk left
return mid
if nums[mid] < x:
lo = mid + 1
else:
hi = mid - 1
return -1Why it's not enough: The trap: with many duplicates the walk left is linear again. When half the log shares one timestamp, this is no better than the scan.
Stage 3 · Polish: Make it lean
Don't stop when you hit x. Search for the boundary instead: keep the half that could still contain the first x. When nums[mid] < x the answer is to the right; otherwise mid might be it, so keep it with hi = mid.
def first_index(nums, x):
lo, hi = 0, len(nums) # hi is exclusive
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] < x:
lo = mid + 1
else:
hi = mid # mid could be the first x
return lo if lo < len(nums) and nums[lo] == x else -1Why it holds up: Optimal whatever the duplicates. This lower-bound shape is what Python's bisect_left does.
X-ray: watch it run
Benchmark: will the forge overheat?
Run all three stages on a large input in your browser and compare the work each one does.
In the interview
Write the loop invariant before the code: "the first x is always in [lo, hi)". It settles the < vs <=, mid vs mid − 1 questions that cause most binary-search bugs.
Go deeper: Binary Search Algorithm · Binary Search on the Answer