Call binarySearch([2, 5, 8, 12, 16, 23, 38, 56, 72, 91], 23) - a new frame is pushed onto the call stack.
primitives are shown in Variables.
Real execution, step by step. Press play or scrub with the controls - every variable and array index updates live.
Throw away half, every time
So far, faster meant 'do fewer steps per item'. Now we meet a completely different idea: what if each step let you IGNORE half of everything that's left? The animation above searches a sorted list for 23 - but watch closely, because it never scans left to right.
Instead it jumps to the middle, asks 'is my target bigger or smaller than this?', and instantly throws away the entire half that can't contain the answer. Then it does the same to what remains. Middle, discard half. Middle, discard half. Press play and watch lo and hi close in on the target like a trap.
Imagine it like this: Finding a word in a dictionary. You don't start at page 1. You open the middle, see you've gone too far, and flip to the middle of what's left. A 2,000-page dictionary is found in about 11 flips.
- sorted
- - arranged in order - the precondition that makes 'discard half' possible
- binary search
- - repeatedly halving a sorted range until the target is pinned down
This is O(log n)
When each step halves what's left, the number of steps is tiny: it's how many times you can cut n in half before you reach 1. That count is called the logarithm of n, so we call this O(log n), 'order log n'.
The numbers feel like magic. 8 items take 3 steps. 1,000 items take about 10 steps. A MILLION items take about 20 steps. A billion? About 30. Every time you double the data, O(log n) adds just ONE more step. Compare that to O(n), which doubles its work when the data doubles. This is the difference between an app that scales to the whole world and one that falls over at ten thousand users.
- Each step throws away half the remaining data
- Steps = how many times you can halve n down to 1 = log n
- 1,000,000 items -> about 20 steps; doubling the data adds just 1 step
- The catch: the data must be sorted first
- O(log n)
- - logarithmic time - halving each step; astonishingly few steps even for huge inputs
The whole ladder, so far
You now have three rungs of the cost ladder, and you can feel the difference between them. O(log n): halve each step, almost free. O(n): look at everything once, fair. O(n squared): look at everything for everything, dangerous. From fastest to slowest, that's the order they'll fall in on any big input.
Nearly every algorithm in the rest of this course is a story about moving DOWN this ladder - taking something that looks O(n squared) and finding the trick, the structure, or the sorted order that drops it to O(n) or O(log n). Now that you can see cost move, you're ready to build the structures that control it.
Imagine it like this: Three ways to find a name in a phone book: check every entry (O(n)), compare everyone to everyone (O(n squared)), or flip to the middle and halve (O(log n)). Same goal, wildly different amounts of work.
Check your understanding
0/3 answeredQ1Binary search works by:
Q2About how many steps does binary search need for 1,000,000 sorted items?
Q3What must be true before you can use binary search?