Binary Search
PlayFind any element in sorted data in O(log n) time
This concept builds on Sorting — Putting Things in Order, Recursion — Functions That Call Themselves. Consider exploring them first for the best experience.
A Sorted Row and One Target
The canvas shows 15 sorted numbers, each cell with its index underneath, and the Target card reads 67. A linear scan would check cells left to right, up to 15 checks. Binary search uses the sorted order instead: the blue bar under the cells marks the search range, which starts as the whole array, indices 0 to 14.
Compare With the Middle
The yellow cell labelled mid sits halfway through the blue range. Compare it with the target: equal means found, smaller means the target can only lie to its right, larger means only to its left. Press 'Next comparison' to step one comparison at a time and read the verdict in the line at the top of the canvas.
Discard Half
After each comparison the cells that cannot hold the target turn dark grey and the blue bar shrinks to the surviving half. Watch the Remaining card: it roughly halves every time. Press 'Previous comparison' to step back and compare the range before and after one test — a single comparison throws away about half the candidates.
Worked Example: 67 in 15 Elements
Target 67 among 15 cells. Comparison 1: mid index 7 holds 45, too small, so keep indices 8 to 14 (7 left). Comparison 2: mid index 11 holds 74, too large, so keep 8 to 10 (3 left). Comparison 3: mid index 9 holds 59, too small, so keep index 10 (1 left). Comparison 4: 67, found. Four comparisons, and log₂15 ≈ 3.9 rounds up to 4.
Choose Your Own Target
Click any cell on the canvas to make its value the new target and watch the search restart. The cell at index 7 is found in a single comparison, because it is the very first mid. Press 'New Target' for a random value. Whatever you try, the Comparisons card never goes past 4 for 15 cells.
Why It Scales: log₂ n
Slide the 'Array Size' slider up to 31 cells and try several targets: the Comparisons card tops out at 5, just one more than for 15 cells. Doubling the array adds only one comparison, because one test halves it straight back. That is O(log n): a million sorted items need at most 20 comparisons, where a linear scan may need a million.
How It Works — Step by Step
-
1
A Sorted Row and One Target
The canvas shows 15 sorted numbers, each cell with its index underneath, and the Target card reads 67. A linear scan would check cells left to right, up to 15 checks. Binary search uses the sorted order instead: the blue bar under the cells marks the search range, which starts as the whole array, indices 0 to 14.
-
2
Compare With the Middle
The yellow cell labelled mid sits halfway through the blue range. Compare it with the target: equal means found, smaller means the target can only lie to its right, larger means only to its left. Press 'Next comparison' to step one comparison at a time and read the verdict in the line at the top of the canvas.
-
3
Discard Half
After each comparison the cells that cannot hold the target turn dark grey and the blue bar shrinks to the surviving half. Watch the Remaining card: it roughly halves every time. Press 'Previous comparison' to step back and compare the range before and after one test — a single comparison throws away about half the candidates.
-
4
Worked Example: 67 in 15 Elements
Target 67 among 15 cells. Comparison 1: mid index 7 holds 45, too small, so keep indices 8 to 14 (7 left). Comparison 2: mid index 11 holds 74, too large, so keep 8 to 10 (3 left). Comparison 3: mid index 9 holds 59, too small, so keep index 10 (1 left). Comparison 4: 67, found. Four comparisons, and log₂15 ≈ 3.9 rounds up to 4.
-
5
Choose Your Own Target
Click any cell on the canvas to make its value the new target and watch the search restart. The cell at index 7 is found in a single comparison, because it is the very first mid. Press 'New Target' for a random value. Whatever you try, the Comparisons card never goes past 4 for 15 cells.
-
6
Why It Scales: log₂ n
Slide the 'Array Size' slider up to 31 cells and try several targets: the Comparisons card tops out at 5, just one more than for 15 cells. Doubling the array adds only one comparison, because one test halves it straight back. That is O(log n): a million sorted items need at most 20 comparisons, where a linear scan may need a million.
Key Takeaways
O(log n) time complexity
Each comparison eliminates half the remaining elements. For one million elements, binary search takes at most 20 comparisons. Linear search would need up to one million.
Requires sorted input
Binary search only works because we can guarantee the target is in one specific half. Without sorted order, we couldn't safely discard half the array each step.
Works on any random-access sorted structure
Binary search applies to any structure where you can index into the middle in O(1) time — arrays, sorted lists in databases, and more.
Connected Concepts
Sorting
Binary search only works on sorted data — sorting is the prerequisite that makes O(log n) search possible.
Recursion
Binary search can be written recursively: each call searches half the remaining range.
Logarithms
The number of halvings it takes to shrink n items down to one is log₂ n — the whole cost of the search.
Binary Search Trees
A binary search tree stores the same midpoint decisions as links, so the search still works as data is inserted.
Big-O Notation
Compare the O(log n) curve of binary search with the O(n) line of a linear scan.
Updated
- — Step through each comparison with Next/Prev, click a target cell, plus a worked example (67 in 15 items)