B2.4 · Searching · Covered

Binary search

Use sorted data to rule out half of the remaining candidates at each step.

55 minutes

For this lesson

Open student handout (PDF) Class activities ↓ Try the example in Python → Homework · due 21 Sept 2026

Watch binary search

Target 42

Sorted values · indices underneath8 candidates

RemainingRuled outChecking

Start with all eight values. Check the middle index, rounding down.

low = 0mid = —high = 7

Python implementation

Highlight = the line just executed. Skipped branches stay unhighlighted.

1def binary_search(items, target):2    low = 03    high = len(items) - 14    while low <= high:5        mid = (low + high) // 26        if items[mid] == target:7            return mid8        elif items[mid] < target:9            low = mid + 110        else:11            high = mid - 112    return -1

Ready to call binary_search(items, 42).

0 values checked

By the end of this lesson

Explain why binary search requires sorted input.
Trace low, mid and high through successful and unsuccessful searches.
Implement binary search and test its boundaries.

Use these activities to review the topic at your own pace. Timings are approximate.

Review the lesson

01 · 5 minutes

Retrieve linear search

Describe the first-match algorithm. How many comparisons might it need for an absent target in a list of 1,000 values?

02 · 10 minutes

Find the middle

Search [3, 8, 12, 17, 23, 31, 42, 56] for 31 by hand. Use zero-based indices, low = 0, high = len(items) - 1 and mid = (low + high) // 2. After a failed comparison, explain which half can be discarded.

03 · 15 minutes

Trace two searches

Build a table with iteration, low, high, mid, items[mid] and next action. Trace a successful search for 31 and an unsuccessful search for 20. Record why the loop stops in each case.

04 · 20 minutes

Implement and test

Write binary_search(items, target), returning a matching index or -1. Continue while low <= high. Test an empty list, a singleton, first and last values, and an absent value. Compare expected and actual results.

05 · 5 minutes

Explain your decisions

Explain why the next boundary is mid + 1 or mid - 1, rather than mid. State what you can guarantee if duplicate values occur.

Space complexity: what are we counting?

Auxiliary space means the extra working memory an algorithm needs, beyond the input it has already been given. Think of it as scratch space: counters, a running total, new lists and the memory used by active function calls.

In the summation example on textbook page 361, numbers is the supplied input list. The algorithm keeps a running total in sum and uses a fixed number of extra variables. Whether the list has 10 items or 10,000, it still needs only those few variables: O(1) auxiliary space.

The textbook’s O(n) space statement counts the input list too: storing n items takes memory that grows with n. That is total space, including the input. Both descriptions can be correct; they count different things.

A larger value in sum does not mean we keep more totals. For this classroom analysis, we treat each number as one fixed-size value. Creating a new copy of all n items, or saving every intermediate total, would instead need O(n) auxiliary space.

When explaining an answer, state your convention: “O(1) auxiliary space; O(n) total space including the input list.” Time is a separate question: visiting every item still takes O(n) time.

Before you leave

Exit question

What makes the search interval shrink, and why would unsorted input break the reasoning?

Homework for this topic

Due 21 Sept 2026 · Problems 1 and 2 + reading · Assigned

Weekend homework: Problems 1 and 2 + reading

Complete Problems 1 and 2 in the algorithms handout, then read the textbook’s binary-search section. Have your work ready for Monday, 21 September.