Binary Search

Play

Find any element in sorted data in O(log n) time

Computer Science Algorithms beginner 8 min

This concept builds on Sorting — Putting Things in Order, Recursion — Functions That Call Themselves. Consider exploring them first for the best experience.

Step 1 of 6

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.

Play Deep Dig A game about Binary Search

How It Works — Step by Step

Step 1 of 6
  1. 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. 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. 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. 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. 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. 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.

Added
Updated
  • — Step through each comparison with Next/Prev, click a target cell, plus a worked example (67 in 15 items)