Using the visualizer
Type a list and what to look for. Binary search only works on a sorted list, so the list is sorted first, and the position in the result is the position in that sorted list. The animation shows the part still in play; everything ruled out fades back. Show the steps lists every check. Words are compared ignoring capitals and accents, so cafe finds Café.
How binary search works
Look at the middle item. If it's the one you want, you're done. If what you want comes before it, the right half can't contain it, so throw that half away; if it comes after, throw away the left half. Then look at the middle of what's left, and repeat.
It's how you'd look up a word in a paper dictionary: open it in the middle, see which side your word is on, and never look at the other side again.
Why it's so fast
Each check halves what's left, so the number of checks grows with the number of times n can be halved. In the worst case binary search needs ⌊log₂ n⌋ + 1 checks: 4 for ten items, 10 for a thousand, and 20 for a million. Linear search could need a million.
John Mauchly described binary search in the Moore School Lectures of 1946.
A worked example
Look for 23 in 2, 5, 8, 12, 16, 23, 38, 56, 72, 91. The middle of the ten is 16, and 23 comes after it, so the first five are out. The middle of the last five is 56, and 23 comes before it, so 56 and everything after it is out. That leaves 23 and 38, and the middle of those is 23. Found, after 3 checks.
Look for 40 in the same list and the first three checks go the same way: 16, then 56, then 23. 40 comes after 23, which leaves only 38. 40 comes after that too, so there's nothing left, and the search ends after 4 checks: 40 isn't in the list. A linear search would have checked all ten to say the same.
In the classroom
Ages 8 and up, about 20 minutes. One pupil thinks of a number from 1 to 100, and the class may only ask "is it bigger than…?". Halving every time finds any number in at most 7 questions. Then try it on a list that isn't sorted, and see why halving stops working.
Take it further: CS Unplugged's searching lessons, "Divide and conquer" and "The Great Number Hunt" in sorted and unsorted versions, are ready-made versions of the same idea for ages 5 to 10.
Questions
Why does the list need to be sorted?
Throwing half away only works if everything on one side of the middle is smaller and everything on the other side bigger. In an unsorted list, the item could be anywhere.
What if the item isn't there?
The part still in play shrinks to nothing, and the search says so, after at most ⌊log₂ n⌋ + 1 checks.
Why does the animation only go up to 3 steps a second?
Each step recolors a bar or two. The web's accessibility guidelines allow anything that flashes three flashes a second at most, and capping the animation at three steps a second keeps it well inside that. Step forward goes as fast as you can click.
Sources
Added . Last updated and reviewed . What's new






