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' has meant doing fewer steps per item. Now meet a completely different, almost magical idea: what if each step let you ignore half of everything that's left? The animation above searches a sorted list for 23 - and watch closely, because it never scans left to right.
Instead it jumps to the middle, asks one question - '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. The pointers 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 flop it open in 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 simply how many times you can cut n in half before you reach 1. Mathematicians call that count the logarithm of n, so we name this cost O(log n), 'order log n'.
The numbers feel unreal. 8 items take 3 steps. 1,000 items take about 10. A million items take about 20. A billion? About 30. Every time you double the data, O(log n) adds just one more step - while O(n) doubles its entire workload. That gap is the difference between an app that serves the whole planet and one that buckles at ten thousand users.
One million sorted items. A linear O(n) scan may open all million boxes. Binary search opens about twenty. Twenty. That is the power of throwing away half every step.
- 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 becomes about 20 steps; doubling the data adds just 1
- The one 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 hold three rungs of the cost ladder, and you can feel the gap 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. Fastest to slowest, that's the order they finish in on any big input.
Nearly every algorithm ahead is a story about climbing 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). You can see cost move now. Next, you'll start building the structures that control it.
Imagine it like this: Three ways to find a name in a phone book: read 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.
Binary search is breathtakingly fast, but it demands sorted data - and sorting itself costs about O(n log n). So it pays off when you search the same data many times, not just once.