The fastest way to search a sorted array — explained through stunning animations. Watch the search space halve every step, try it yourself, and see why it's O(log n).
// WHAT YOU'LL LEARN
// DEFINITION
Binary search is an algorithm for finding a target in a sorted array. It looks at the middle element. If the middle is the target, done! If the target is smaller, throw away the right half. If larger, throw away the left half. Repeat on the remaining half.
Each step cuts the search space in half. So for an array of size n, you need only about log₂(n) steps — that's blazingly fast even for billions of elements.
// THE 3 KEY IDEAS
Three core ideas power binary search. Understand these and you understand the algorithm.
Binary search only works on sorted data. The order lets us decide which half to discard by comparing to the middle.
SEE IT BELOW ↓✂️IDEA 2Compare the target to the middle. Discard the half that cannot contain the target. The search space shrinks by 2× each step.
ANIMATED BELOW ↓⚡IDEA 3Halving repeatedly means ~log₂(n) steps. 1 million items → 20 checks. 1 billion → 30. Astonishingly fast.
COMPARE BELOW ↓// WATCH IT IN ACTION
Pick a target below and press play. Watch how the search space halves every step until the target is found — or proven missing. The narration explains each move.
You want to find "Smith" in a 1000-page phone book. You don't flip page by page from the start — that would take forever! Instead, you open the book in the MIDDLE. S comes after M, so you tear the book in half and throw away the front. Open the middle again... repeat. Each time you throw away HALF the pages. That's binary search!
Press PLAY to start the search!
// HOW IT WORKS — STEP BY STEP
Look at the element in the middle of the current search range (lo to hi).
Is the middle equal to, less than, or greater than the target?
Equal → done! Smaller → search the right half. Larger → search the left half.
Keep halving until you find the target, or lo > hi (not present).
Each step halves the search space: n → n/2 → n/4 → ... → 1. The number of halvings to reach 1 is log₂(n). So for n = 1,000,000, that's about 20 steps. For n = 1,000,000,000, only ~30. The search space collapses exponentially fast.
// FLOWCHART · ALGORITHM VISUALIZATION
Press PLAY to trace the algorithm through the flowchart.
// PSEUDOCODE · EXECUTION FLOW
Press PLAY to step through the algorithm line by line.
// TRY IT YOURSELF
Enter your own sorted array and a target. Watch the full step-by-step trace of lo, hi, and mid at each comparison. Try a target that isn't there to see how binary search proves absence efficiently.
// LINEAR VS BINARY
Drag the slider to change the array size. See how linear search grows with N while binary search barely grows at all. This is the power of logarithmic time.
Check every element one by one.
Halve the search space each step.
16 items → linear needs 16 checks, binary needs only 5. That's 3× faster!
| Array size (n) | Linear (n) | Binary (⌈log₂ n⌉+1) | Speedup |
|---|---|---|---|
| 16 | 16 | 5 | 3× |
| 1,000 | 1,000 | 11 | 91× |
| 1,000,000 | 1,000,000 | 21 | 47,619× |
| 1,000,000,000 | 1,000,000,000 | 31 | 32,258,065× |
// PROPERTIES
Binary search ONLY works on a sorted array. If the data is unsorted, you must sort it first — or use linear search instead.
Each comparison halves the search space. For 1 billion items, you need only ~30 checks. For 1 trillion, only ~40. It scales beautifully.
Binary search is the simplest example of the divide-and-conquer paradigm — the same idea behind merge sort and quicksort.
It underlies countless algorithms: balanced BSTs, exponentiation by squaring, finding roots, and optimization via binary search on the answer.
// DID_YOU_KNOW
John Mauchly (co-creator of ENIAC) mentioned binary search in 1946, but a correct version with proper bounds wasn't published until 1962.
A famous 2006 study by Joshua Bloch found that nearly all implementations had bugs in edge cases — overflow, off-by-one, or infinite loops.
Computing mid as (lo + hi) / 2 can overflow for huge arrays. The safe way is lo + (hi - lo) / 2, or the bit-shift lo + ((hi - lo) >> 1).
Dictionary lookups, database indexes, git bisect, autocomplete, auto-tuning, finding square roots — binary search is everywhere.
When the answer is a number in a range and you can test "is it achievable?", you can binary search the answer itself — a technique called "binary search on answer".
A million sorted numbers can be searched in just 20 comparisons. A billion in 30. This is why logarithmic time is almost as good as instant.
// PRACTICE & ASSESS
Now that you've learned the concept, put it into practice. Solve coding problems and take quizzes to reinforce what you've learned.
// TUTORIAL QUIZZES · LEVELS 1–9
Nine progressive quizzes from Level 1 to Level 9. Each has 10 questions with a 10-minute timer. XP scales with level — L1 gives 10 XP, L9 gives 90 XP. Click a quiz to expand and begin.
// REFERENCES
// READY?
Practice 10,000+ coding problems, follow career roadmaps, and get hired.