Core · AlgorithmsLesson 5 of 8Free to read

Binary search · Data Structures and Algorithms

How do you search a sorted list of a million items in 20 steps?

Why you need it

Guess a number between 1 and 1,000,000 with "higher/lower" hints and you need at most 20 guesses, if you always guess the middle. That idea, binary search, is behind database indexes, git bisect and countless interview problems.

The intuition

Keep a range [lo, hi] where the answer must be. Look at the middle:

equal → found
middle is too small → the answer is to the right: lo = mid + 1
too big → to the left: hi = mid - 1

Each step halves the range, so it takes about log₂ n steps: 20 for a million, 30 for a billion. The list must be sorted.

Definition

Binary search

Searching a sorted range by comparing with the middle and discarding half each time. O(log n).

Invariant

A fact that stays true on every loop step, here: "if the target exists, it is between lo and hi". Writing it down prevents off-by-one bugs.

Examples

Binary search, step by step

Try it yourself

Print each range so you can watch it shrink.

def search(xs, target):
    lo, hi = 0, len(xs) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        print("look at", mid, xs[mid])
        if xs[mid] == target:
            return mid
        if xs[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

print(search([2, 5, 8, 12, 16, 23, 38, 56, 72, 91], 23))

Step by step

L4Middle of 0..9 is 4: value 16.
L916 < 23, so the answer is right of 4.
L11Range 5..9, middle 7 is 56: too big.
L14Range 5..6, middle 5 is 23. Found in 3 looks.5

Common mistakes

while lo < hi with hi = mid - 1

Mixing loop conditions and updates from different templates skips the last candidate. Pick one template and keep the invariant in mind.

Unsorted input

On an unsorted list binary search returns wrong answers without any error. Sort first, or don't use it.

Quick quiz

1. About how many steps does binary search need for 1,000,000 sorted items?

A20
B1,000
C500,000

Show the answer

Answer: A

2²⁰ ≈ 1,000,000, so 20 halvings.

2. What does this print?

1
2
3

import bisect
scores = [55, 61, 70, 70, 84, 92]
print(bisect.bisect_left(scores, 70), bisect.bisect_right(scores, 70))

A
```
2 4
```
B
```
2 3
```
C
```
3 4
```

Show the answer

Answer: A

bisect_left: first position where 70 could go (2). bisect_right: after the last 70 (4).

Practice

3 exercises in three steps: predict what a program prints, change a program to meet a new requirement, then write one from scratch. Your code runs in the browser and is checked the moment you submit.

PredictCount the looks
Type exactly what this program prints.
ModifyFix the endless search
This binary search loops forever when the target is bigger than the middle. Fix the update so the range always shrinks.
WriteFirst bad version
Versions 1…n were released; from some version on, every version is bad. is_bad(v) tells you whether version v is bad. Write first_bad(n, is_bad) that returns the first bad version using binary search (the tests count your calls). Assume version n is bad.

Practise this lesson

Open the interactive lesson to edit and run these examples and solve the exercises with instant feedback. Free to start, no sign-up.

Open the interactive lesson Course map

Interactive lessons open in order. If you have not done the earlier ones yet, you start at the course map.

Terms in this lesson

Term	Chinese	Definition
Binary search	二分查找	Halving a sorted range at each step to find a target in O(log n).
Invariant	不变式	A fact that stays true on every step of a loop.