How to Animate Binary Search | QuantumSketch
Animate binary search by halving a sorted array each step: check the middle, discard the wrong half, repeat. The shrinking window shows the O(log n) speed.
Animate binary search by halving a sorted array each step: check the middle element, discard the half that can't contain the target, and repeat. The window collapsing from a million to one in ~20 steps is the O(log n) lesson.
The precondition
Binary search requires a sorted array. (Need to sort first? See Visualize Sorting Algorithms.)
The animation, beat by beat
- Show a sorted row of boxes; mark
lowandhighat the ends. - Check the middle. Compare it to the target.
- Discard a half — if middle is too small, fade the left half; too big, fade the right.
- Repeat on the surviving window — it halves each time.
- Land on the target (or report "not found" when the window is empty).
Why it's fast
| Array size | Linear scan (worst) | Binary search | |---|---|---| | 1,000 | 1,000 | ~10 | | 1,000,000 | 1,000,000 | ~20 |
Each comparison halves the candidates: log₂(1,000,000) ≈ 20. Animating both side by side, with counters, dramatizes O(log n) vs O(n).
Manim building blocks
A row of Squares with labels, low/mid/high pointer Arrows, FadeOut for the discarded half, and an Integer comparison counter.
The prompt
"Animate binary search for 73 in a sorted 16-element array: mark low/mid/high, fade out the discarded half each step, and count comparisons."
→ Render it at quantumsketch.app. Related: Animate Merge Sort.
Written by Shihab Shahriar Antor · Shahriar Labs
FAQ
Q.What's the clearest way to animate binary search?
Show a sorted row of boxes with a search window that halves each step. Mark the low and high ends of the window, check the middle element, and compare it to the target. If the middle is too small, discard the entire left half by moving low past the middle; if too big, discard the right half. Animating the discarded half fading out each step makes it obvious that the search space shrinks by half every comparison, so even a million-element array is found in about 20 steps. Contrasting it with a linear scan checking every box dramatizes the O(log n) versus O(n) difference.
Q.Why is binary search so much faster than scanning the array?
Because it eliminates half the remaining elements with each comparison instead of one. Linear search checks elements one at a time, so finding an item in a million-element array can take up to a million comparisons. Binary search halves the candidates each step, so it needs only about log₂(1,000,000) ≈ 20 comparisons. The catch is that binary search requires the array to be sorted first. Animating both methods on the same large sorted array, with comparison counters, makes the logarithmic advantage concrete and memorable.