Skip to content

level 2 · Searching

Binary Search

Throw away half the list with every single question.

10 min 70 XP

what is it

Start here

Binary search asks one question — 'is the middle too big or too small?' — and throws away half of everything based on the answer.

It only works on a sorted list. That is not a limitation, it's the whole trick: because the list is sorted, looking at one item tells you something about *all* the items around it. If the middle is too small, then everything to its left is also too small. Gone. You never look at them.

The result is almost unfair. Doubling the size of the list adds just one extra look. A list of 1,000 takes about 10 looks. A million takes 20. A billion takes 30. Watch the counter in the visualization and try it on a big list — that is not a typo.

real-life analogy

Picture it

Finding a word in a dictionary

You don't start at page 1 and read forwards. You flop it open near the middle, see you've landed on 'M', and if you want 'Rabbit' you throw away the entire first half of the book without a second thought. Then you do it again. Nobody taught you this — it's just obvious once the words are in order.

interactive visualization

Watch it run

Type a list (it gets sorted for you) and a number to find.

  1. 3
    0
  2. 7
    1
  3. 12
    2
  4. 18
    3
  5. 24
    4
  6. 31
    5
  7. 40
    6
  8. 55
    7
  9. 63
    8
  10. 77
    9
  11. 82
    10
  12. 91
    11

Looking for 63 in a sorted list. Because it is sorted, we can throw away half of it with a single question.

step 01/6

  • found it
  • ruled out
1function binarySearch(a, target) {
2 let low = 0;
3 let high = a.length - 1;
4 while (low <= high) {
5 const mid = Math.floor((low + high) / 2);
6 if (a[mid] === target) return mid;
7 if (a[mid] < target) low = mid + 1;
8 else high = mid - 1;
9 }
10 return -1;
11}

variables right now

target
63
size
12
comparisons 0moves 0

the dry run · every step, in words

6 steps

complexity

What it costs

best case
O(1)
average
O(log n)
worst case
O(log n)
extra memory
O(1)

Every look halves what's left. To go from 1,000,000 items to 1 you only need to halve about 20 times — so 20 looks is the *worst* case on a million items.

  • O(1)
  • O(log n) · this one
  • O(n)
  • O(n log n)
  • O(n²)
input size →work →

common mistakes

Common traps

  • Running binary search on an unsorted list.

    It will confidently return the wrong answer. Sorted order is the assumption that makes 'throw away half' valid — without it, the algorithm is nonsense.

  • Writing `while (low < high)` instead of `while (low <= high)`.

    With `<`, the window can shrink to a single box and you never look at it — so you miss values that were right there. The window is only truly empty once low passes high.

  • Computing the middle as (low + high) / 2 in a language with fixed-size integers.

    On huge arrays low + high can overflow and go negative. Use low + (high − low) / 2. This exact bug sat in the Java standard library for nine years.

  • Forgetting the +1 and −1 when narrowing the window.

    You already checked the middle. If you set low = mid instead of mid + 1, the window stops shrinking and your program hangs forever.

quiz

Check yourself

Three questions. Get them all right to finish the lesson.

+70 XP

01A sorted list has 1,000,000 items. What is the worst-case number of looks?

02Why does binary search insist the list is sorted?

03You double the list from 1,000 to 2,000 items. How many extra looks does binary search need?

practice

Solve it on LeetCode

You've seen it run — now write it yourself. These are real LeetCode problems that use exactly this idea, from gentlest to toughest.