Halving the Search: Classic Binary Search
A raffle has sold a million tickets, and their numbers are stored in sorted order. Someone asks whether ticket 730,512 was sold. Reading the list from the start could take a million checks. Opening it in the middle, seeing which half the number must be in, and repeating takes about twenty.
The rule
Sorted? Check the middle and throw away the half that cannot hold it.
Keep two bounds, lo and hi, around the part of the list that could still contain the target. Look at the middle item. If it is the target, you are done. If it is too small, the target can only be to its right; if too big, only to its left. Either way, half the remaining list is gone after one comparison.
def find(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi: # the window still holds at least one item
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
if nums[mid] < target:
lo = mid + 1 # target can only be right of mid
else:
hi = mid - 1 # target can only be left of mid
return -1The idea that keeps this correct is an invariant, a promise that is true before every loop: if the target is in the list at all, it lies between lo and hi. Every update keeps the promise, and when lo passes hi the window is empty, so the target is not there. The + 1 and - 1 matter too: mid has already been checked, so it leaves the window.
The shortcut
To estimate the cost, count how many times you can halve n before one item is left. 1,000 halves to 1 in about 10 steps; 1,000,000 in about 20; a billion in about 30. That number is log₂ n, and it is why binary search barely notices the size of the list.
Window 0 to 6
The middle is position 3, value 21. Too small, so the 30 must be to the right:
lo = 4.
The trap is the off-by-one family: writing lo = mid instead of mid + 1 can leave the window stuck on one item forever, and while lo < hi stops one item early, so a one-item window is never checked.
Drills
Answer fast — trust the rule.
At most how many middles does find check in a sorted list of 1,000 items?
What does find([4, 9, 13, 21, 30, 42, 57], 5) return?
The loop is changed to while lo < hi. What does find([5], 5) return now?
The middle item is bigger than the target. Why is hi = mid - 1 safe rather than hi = mid?
Remember
- Sorted? Check the middle and throw away the half that cannot hold it.
- Shortcut: the cost is how many times n halves to 1, about 20 for a million.
- Trap: off-by-one bounds;
midleaves the window, and the loop runs whilelo <= hi.