Binary Search
Halving a sorted list.
Open a dictionary to find the word mango. You don't start at A. You open somewhere in the middle, see you're at P, and go left. Each look throws away half the book. That's binary search, and it only works because the words are sorted.

- Find 'mango' in a dictionary
- Open the middle, go left or right
- It needs sorted data
Binary search, step by step
Low and high mark the part of the list that could still hold the target. We look at the middle item. If it's the target, we're done. If it's too small, the target must be to the right, so low moves past the middle. If it's too big, high moves left. We print each step. Run it. Just three looks, to find twenty three among sixteen numbers. For a million numbers, it's never more than about twenty.
def binary_search(nums, target):
low, high = 0, len(nums) - 1
while low <= high:
mid = (low + high) // 2
print(f" look at index {mid}: {nums[mid]}")
if nums[mid] == target:
return mid
if nums[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
nums = [2, 5, 8, 12, 16, 23, 38, 45, 56, 72, 91, 95, 99, 104, 110, 120]
print("found at", binary_search(nums, 23))look at index 7: 45 look at index 3: 12 look at index 5: 23 found at 5
Binary search rules
The list must be sorted, or binary search gives wrong answers, with no warning. It's O of log N, which is incredibly fast. And it returns minus one, or none, when the target isn't there. The loop condition, low less than or equal to high, is where most bugs hide.
| key | value |
|---|---|
| Needs | sorted data |
| Speed | O(log n) |
| Not found | return -1 |
| Bug magnet | low <= high, mid ± 1 |
Summary
Binary search halves a sorted list at every step, so it's O of log N. Next, Python's built in binary search, and tricky edge cases.
Key takeaways- Sorted data only
- Look at the middle
- Halve each step