Learn · DSA · Pattern 4
Binary Search
On sorted data, you never scan — you halve. Each guess throws away half of what’s left, so even a million items fall in about 20 steps.
Before we start
📋 What you’ll learn
- Why halving a sorted range gives O(log n)
- The safe binary-search template (lo, mid, hi)
- The classic bugs and how to avoid them
- The “binary search on the answer” trick
✅ After this you’ll be able to
- Find any value in a sorted array in ~20 steps at a million items
- Handle “first/last position” and threshold questions
- Explain why it only works on sorted data
Why you’re learning it: it’s the purest example of O(log n), a constant interview favourite, and the idea behind database index seeks and git bisect. ⏱️ ~25 min. Do Big-O first.
The idea
You know the game: “guess my number, 1 to 100.” You don’t start at 1 — you guess 50. “Higher.” Guess 75. “Lower.” Every guess halves the range. That halving is O(log n): 100 numbers take ~7 guesses, a million take ~20. The one rule: the data must be sorted, because “higher/lower” only makes sense when things are in order.
Watch it work — find 9
Sorted array. lo and hi bound the range; mid is the guess.
1 0 lo
3 1
5 2
7 3 mid
9 4
11 5
13 6 hi
mid = 7. 7 < 9, so the answer is to the RIGHT. Move lo past mid.
1 0
3 1
5 2
7 3
9 4 lo
11 5 mid
13 6 hi
mid = 11. 11 > 9, so the answer is to the LEFT. Move hi below mid.
1 0
3 1
5 2
7 3
9 4 lo/mid/hi
11 5
13 6
mid = 9. Found it at index 4! ✅
Faded cells are already thrown away. Three steps to find it in a 7-element array — and it barely grows as the array does.
The safe template
lo = 0, hi = n - 1
while lo <= hi:
mid = lo + (hi - lo) / 2 // avoids overflow
if arr[mid] == target: return mid
if arr[mid] < target: lo = mid + 1
else: hi = mid - 1
return -1 // not foundClassic bugs (know these)
- Off-by-one: forgetting
mid + 1/mid - 1→ infinite loop. Always move past mid. - Overflow:
(lo + hi) / 2can overflow on huge inputs; uselo + (hi - lo) / 2. - Unsorted data: binary search on unsorted input silently returns nonsense. Sort first, or don’t use it.
Where you’ll use it — real life
🗂️ Database indexes
A DB finds a row by an indexed key with a binary-search-like seek instead of scanning millions of rows.
🐙 git bisect
Finding which commit introduced a bug: git halves the history, testing the middle each time. Pure binary search.
🎯 Search on the answer
“What’s the smallest capacity that ships everything in D days?” Binary-search the answer instead of the array — a powerful advanced move.
📚 Any sorted lookup
Autocomplete, leaderboards, version tables — sorted data means log-time lookups.
Why we practice this
The concept is one sentence; the correct implementation (the boundaries) is where everyone slips. Reps burn the template in so you write it bug-free under pressure.
Now YOU do the reps
🗣️ The 2-minute explain test
Out loud: “Why is binary search O(log n), and why does it only work on sorted data?” Then log it in your Journal.
Next: Linked Lists →