Binary search
Halving a sorted array each step to find a value in O(log n). · 7 min read
If the array is sorted, you don't have to check every element. Look at the middle: if the target is smaller, it must be in the left half; if larger, the right half. Either way you discard half the array in one comparison, and repeat.
def binary_search(a, target):
lo, hi = 0, len(a) - 1
while lo <= hi:
mid = (lo + hi) // 2
if a[mid] == target: return mid
if a[mid] < target: lo = mid + 1
else: hi = mid - 1
return -1Interactive visualization: Shrinking the search window with lo / mid / hi — step through it frame by frame on this page.
The loop invariant
A loop invariant is a fact that stays true before and after every iteration. For binary search, the invariant is: if the target exists, it is inside the current window `lo..hi`. Initially that window is the whole array. Each comparison discards only a half that cannot contain the target, so the invariant remains true. When the window is empty, the invariant tells us the target is absent.
Why it's O(log n)
Count how many times you can halve the search window before it's empty:
start with n candidates— The whole array is in play.n → n/2 → n/4 → … → 1— Each comparison halves the window.after k steps: n / 2ᵏ = 1— Stop when one candidate remains.2ᵏ = n ⟹ k = log₂ n— Solve for the step count k.
Result: O(log n)
Interactive visualization: Each comparison halves the window — step through it frame by frame on this page.