A. Programming Concepts and Skills · Algorithm Design and Analysis

Binary Search: Halving the Problem

A3.2 C2.1 C2.2About 75 minutes

Learning goals

I can explain why binary search needs sorted data (its precondition).
I can write an iterative binary search with low, high and mid, and trace it in a table.
I can avoid the classic binary search bugs (wrong loop condition, infinite loops, unsorted input).
I can adapt binary search to find the first occurrence or the insertion point of a value.

Words to know

binary search
A search of a sorted array that compares the target with the middle element and discards the half that cannot contain it, repeating until it is found or the range is empty.

low, high
The indexes at the two ends of the part of the array that might still contain the target.

mid
The middle index of the current range, (low + high) // 2.

search range (interval)
The elements from a[low] to a[high]; it shrinks by about half on every pass.

insertion point
The index where a value would go to keep a sorted list sorted.

bisect
Python's standard module of binary-search functions for sorted lists (bisect_left, bisect_right, insort).

Guess my number

"I'm thinking of a number from 1 to 100." You could guess 1, 2, 3, … (linear search, up to 100 guesses). Or you could guess 50. "Higher." Now only 51 to 100 are possible: one guess removed half the numbers. Guess 75. "Lower." Now 51 to 74. Keep guessing the middle, and you will never need more than 7 guesses.

That strategy is binary search, one of the most important algorithms in computer science. It is how a database finds one record among millions, how git bisect finds the change that introduced a bug, and how you look up a word in a paper dictionary.

Each guess is the middle of the shaded range (vertical line). Every answer of "higher" or "lower" cuts the range roughly in half: 100, 50, 24, 12, 5, 2 numbers. The number 66 is found on guess 6.

The algorithm

Precondition: the array a is sorted in ascending order. (This is essential: "higher" only tells you something if the numbers are in order.)

Set low = 0 and high = len(a) - 1. The target, if present, is somewhere in a[low] to a[high].
While low <= high (the range is not empty):

mid = (low + high) // 2
If a[mid] == target: found, return mid.
If a[mid] < target: the target can only be to the right, so low = mid + 1.
Otherwise (a[mid] > target): it can only be to the left, so high = mid - 1.

The range is empty: return −1.

Loop invariant: if the target is anywhere in a, it is in a[low..high]. Each pass keeps this true because it only discards elements that are too small (left of a smaller mid) or too large (right of a bigger mid). When the range is empty, the target cannot be anywhere.

def binary_search(a, target):

"""Return an index i with a[i] == target, or -1.

Precondition: a is sorted in ascending order.

Postcondition: a is unchanged; if target occurs in a, the

result is an index of target, otherwise -1.

"""

low = 0

high = len(a) - 1

while low <= high:

mid = (low + high) // 2

if a[mid] == target:

return mid

elif a[mid] < target:

low = mid + 1

else:

high = mid - 1

return -1

a = [3, 8, 12, 19, 23, 31, 38, 47, 52, 60, 66, 71, 80, 88, 95]

print(binary_search(a, 66), binary_search(a, 3), binary_search(a, 95), binary_search(a, 20))

Output: 10 0 14 -1. Found at index 10, the first index and the last index, and −1 for a missing 20. Each search took at most 4 passes for 15 elements.

Tracing binary search

A trace table records low, high, mid and a[mid] on each pass. This is how you check binary search by hand, and how test questions ask about it.

Pass	low	high	mid	a[mid]	Decision
1	0	14	7	47	47 < 66: low = 8
2	8	14	11	71	71 > 66: high = 10
3	8	10	9	60	60 < 66: low = 10
4	10	10	10	66	equal: return 10

Searching for 66 in the 15-element list. The answer is found on pass 4.

Pass	low	high	mid	a[mid]	Decision
1	0	14	7	47	47 > 20: high = 6
2	0	6	3	19	19 < 20: low = 4
3	4	6	5	31	31 > 20: high = 4
4	4	4	4	23	23 > 20: high = 3
end	4	3			low > high: return -1

Searching for 20, which is missing. After 4 passes low (4) is greater than high (3): the range is empty.

The same search for 66 drawn as pointers. Shaded cells are the current range; the middle element (yellow) is compared; crossed-out cells have been ruled out. Each pass halves the range: 15, 7, 3, 1 elements.

How many passes?

Each pass at least halves the range. Starting with n elements, after k passes at most n ÷ 2ᵏ remain. The search must end when fewer than 1 element remains, so the number of passes is at most about log₂ n + 1. Precisely, the worst case is the number of binary digits of n:

n = 15: 4 passes (15 → 7 → 3 → 1).
n = 1000: 10 passes.
n = 1 000 000: 20 passes.
n = 1 000 000 000: 30 passes.

Binary search is O(log n). Linear search on a billion elements can take a billion comparisons; binary search takes at most 30 passes. The next lesson compares the two carefully, including the cost of keeping the data sorted.

The classic bugs

Binary search is short, but famous for subtle bugs. Check your code against this list:

while low < high instead of <=: when the range shrinks to one element, the loop stops without checking it. Searching for 95 in the list above would wrongly return −1.
low = mid or high = mid instead of mid + 1 / mid - 1: when low and high are next to each other, mid equals low, nothing changes, and the loop runs forever.
Unsorted data: the algorithm runs without any error and gives wrong answers. That is a broken precondition, not a bug in the search.
Using / instead of //: mid becomes a float and a[mid] raises TypeError.

(In languages with fixed-size integers, such as Java or C, (low + high) / 2 can even overflow for huge arrays; programmers write low + (high - low) / 2. Python integers never overflow, so (low + high) // 2 is safe here.)

Worked example

Finding the first occurrence

With duplicates, the basic binary search returns an index of the target, not necessarily the first. In a = [2, 4, 4, 4, 4, 7, 9], binary_search(a, 4) returns 3. Change the algorithm so it returns the first index of the target (here 1).

When a[mid] == target, do not return. Record mid as the best answer so far, and keep searching the left half for an earlier copy: high = mid - 1.
The loop ends when the range is empty; return the recorded answer (−1 if the target was never seen).
def first_index(a, target): low, high = 0, len(a) - 1 answer = -1 while low <= high: mid = (low + high) // 2 if a[mid] == target: answer = mid high = mid - 1 elif a[mid] < target: low = mid + 1 else: high = mid - 1 return answer
Trace with target 4: low 0, high 6, mid 3 (equal: answer 3, high 2); mid 1 (equal: answer 1, high 0); mid 0 (2 < 4: low 1); low > high, stop. Returns 1.
It is still O(log n): each pass halves the range, and it never stops early.

first_index([2, 4, 4, 4, 4, 7, 9], 4) returns 1. The key change is "record and keep going left" instead of returning on equality.

The insertion point, and Python's bisect module

If the target is missing, binary search still knows something useful: when the loop ends, low is the index where the target would go to keep the list sorted (the insertion point). For 20 in the list above, low ended at 4: 20 belongs between 19 (index 3) and 23 (index 4).

Python's standard bisect module does this for you:

bisect.bisect_left(a, x): the first index where x could be inserted (before any copies of x). If x is present, this is its first index.
bisect.bisect_right(a, x): the index just after the last copy of x.
bisect.insort(a, x): inserts x in sorted position (it finds the spot in O(log n), but shifting elements is still O(n); see Subprograms to Insert and Delete Array Elements).

import bisect

a = [3, 8, 12, 19, 23, 31, 38, 47]

print(bisect.bisect_left(a, 20), bisect.bisect_left(a, 23), bisect.bisect_right(a, 23))

names = ["Abdi", "Chen", "Jasmine", "Kateri", "Noah", "Sofia"]

i = bisect.bisect_left(names, "Kateri")

print(i, i < len(names) and names[i] == "Kateri")

Output, one line each: 4 4 5, 3 True. Strings compare in dictionary order by character codes (see Non-Numeric Comparisons: Comparing and Sorting Strings), so binary search works on a sorted list of names too. The last line is the standard way to test membership with bisect: check that the index is in range and holds the target.

Searching records by key

To binary search a list of records, the list must be sorted by the key you search on. A list of students sorted by last name cannot be binary searched by student number. Many programs keep a separate sorted list of keys (or an index) for each field they search often, which is exactly what database indexes do.

Just for fun

I asked binary search for directions to the arena. It said, "You're halfway there." Then it said it again. And again. And again.

Six "halfway theres" later, I was at the door.

Hands-on activity

Dictionary dive and the guessing bot

You need: a paper dictionary or a thick phone directory or catalogue (any alphabetical book), a partner, paper, and a computer with Python.

Dictionary dive. Your partner picks a word. Find it by always opening to the middle of the pages that are left, deciding "earlier" or "later", and ignoring the other half. Count the openings. (A 1000-page dictionary should take at most about 10.)
Compare: how many page turns would it take to find "zebra" by turning one page at a time from the front?
Guessing bot. Write a program where you think of a number from 1 to 1000 and the computer guesses, using low, high and mid. You answer with h (higher), l (lower) or c (correct). Make it print how many guesses it used.
Play 5 rounds. Was it ever more than 10 guesses? (It should not be: 2¹⁰ = 1024 ≥ 1000.)
Try to "cheat" by changing your number in the middle of a round. What does the bot do? Which precondition did you break?

What to look for: the bot must update low = mid + 1 on "higher" and high = mid - 1 on "lower". If you cheat, the range eventually becomes empty (low > high) and the bot should say so instead of crashing or looping forever.

Your turn

What is the precondition of binary search, and what happens if it is broken?

Trace binary_search(a, 38) on the lesson's 15-element list: give low, high and mid for each pass.

At most how many passes does binary search need for n = 500? For n = 4000?

Why does low = mid (instead of mid + 1) cause an infinite loop?

Why does while low < high: miss some targets?

What does bisect.bisect_left([10, 20, 30, 40], 25) return, and what does it mean?

More practice: warm-up

Compute mid for low = 4 and high = 9.

After comparing a[mid] < target, which half is kept, and how do low and high change?

Can you binary search ["pear", "apple", "kiwi"] for "kiwi"? Why or why not?

What is the Big-O of binary search?

What does binary search return in this lesson when the target is missing?

More practice: on your own

Trace first_index([1, 3, 3, 3, 8], 3) (low, high, mid, answer each pass).

Write last_index(a, target) that returns the last index of target in a sorted list, or −1.

Using bisect_left and bisect_right, how can you count copies of x in a sorted list in O(log n)? Compute it for x = 4 in [2, 4, 4, 4, 4, 7, 9].

Predict the output:

a = [5, 10, 15, 20, 25, 30]

low, high = 0, len(a) - 1

passes = 0

while low <= high:

passes += 1

mid = (low + high) // 2

if a[mid] == 12:

break

elif a[mid] < 12:

low = mid + 1

else:

high = mid - 1

print(passes, low, high)

A list of 200 student records is sorted by last name. Can you binary search it for a student number? Explain.

Challenge

Write a recursive binary search bsearch(a, target, low, high). (You will study recursion in Thinking Recursively: Base Cases and the Call Stack; try it now.)

Prove that binary search always stops (no infinite loop) when written correctly.

A sorted list of 1 000 000 numbers has been rotated: e.g. [40, 50, 60, 10, 20, 30]. Describe how to find the index of the smallest element in O(log n).

Check your understanding

Quiz

What must be true before binary search is used?

low = 3 and high = 10. What is mid?

At most how many passes does binary search need for 1000 elements?

A binary search uses while low < high:. What goes wrong?

In a sorted list, the target is less than a[mid]. What does the algorithm do?

bisect.bisect_left([1, 3, 3, 5], 3) returns:

Which loop invariant explains why binary search is correct?

For parents and teachers

Big idea: This lesson completes A3.2 (create linear and binary search algorithms). Writing the precondition and loop invariant continues C2.1, and counting passes (log₂ n) prepares for the full comparison in C2.2.

How to help: Play "guess my number" from 1 to 1000. Ask your teen to predict the maximum number of guesses (10) before you start. Then try the dictionary dive together.

Common difficulties:

Forgetting that the data must be sorted (and sorted by the search key).
Off-by-one errors: < instead of <=, or mid instead of mid ± 1. Insist on a trace table for a target at each end and a missing target.
Using / instead of // for mid.
Expecting the basic version to return the first duplicate.