Unit 4 · Algorithms & Simulation · Lesson 4.4

Binary Search

Check the middle, throw away half, repeat. Sixteen items in five checks, a million in twenty — as long as one thing is true about the list. That one thing is half of every exam question about it.

Big Idea 3 — Algorithms & ProgrammingCED 3.11 · precondition: sorted

Before this lesson

No reading — this page is the reading. Runestone doesn’t cover Unit 4 (search, efficiency, limits, simulation), so everything you need is right here.

1

Where We Are

People→ Bits→ Programs→ Internet→ Security→ Big Data→ Impact

Programs, Algorithms region. Yesterday’s linear search worked on anything and paid for it: n checks. Today’s algorithm is dramatically faster — and it only works under one condition, which the exam tests just as often as the algorithm itself.

2

The Hook

I’m thinking of a number from 1 to 100. Guess it. After each guess you’ll hear “higher” or “lower.” Keep count.

Someone always starts at 1. Someone always does it in 7 or fewer. The difference between those two people is today’s whole lesson.

your guess:
3

The Idea

Picture a phone book (or a dictionary). Open it to the middle. The name you want is either on this page, before it, or after it — so you can tear the book in half and throw away the wrong half. Repeat. A 1,000-page book is down to one page in about 10 tears.

That’s binary search: check the middle element; if it’s not the target, discard the half the target can’t be in; repeat on what’s left.

The precondition: the list must be SORTED. Throwing away half only makes sense if everything smaller is on one side and everything bigger is on the other. On unsorted data, binary search can throw away the half that holds the answer and report “not found” for a value that’s right there. The exam asks about this as often as it asks how the algorithm works.

Python

def binary_search(items, target):
    low = 0
    high = len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid
        if target < items[mid]:
            high = mid - 1  # keep left half
        else:
            low = mid + 1   # keep right half
    return -1

AP Pseudocode

PROCEDURE binarySearch(items, target)
{ low ← 1
  high ← LENGTH(items)
  REPEAT UNTIL (low > high)
  { mid ← (low + high - ((low + high) MOD 2)) / 2
    IF (items[mid] = target)
    { RETURN (mid) }
    IF (target < items[mid])
    { high ← mid - 1 }
    ELSE
    { low ← mid + 1 } }
  RETURN (-1) }

Hover or tap a line to light its twin. Line 4 is the loop flip again — while low <= high becomes REPEAT UNTIL low > high. Line 5: AP Pseudocode has no “round down” division, so subtracting MOD 2 first makes the sum even. You will never have to write binary search on the exam — you’ll have to reason about it.

4

Try It — Halve It

Sixteen sorted numbers. Pick a target and press Check middle. Watch the live range (bright) shrink by half each time. Then flip the list to unsorted and watch it fail.

find:

Try every target on the sorted list: you’ll never need more than 5 checks for 16 items. Linear search’s worst case on the same list is 16.

Lab 4.3, Parts 2–4

Build binary_search with a counter, run the same tests as Part 1, fill the binary column of your table, then break it on an unsorted list (Part 4).

5

Vocabulary

binary search Programs
Repeatedly checking the middle element of a sorted list and discarding the half that can’t contain the target.
sorted Programs
In order — each element is no bigger than the one after it (or alphabetical, for text).
precondition Programs
Something that must be true before an algorithm can be used correctly. Binary search’s precondition: the data is sorted.
6

Check

Five questions. The first one is nearly free points — if you remember one word.

0 of 5 answered
7

Impact Check

Someone has to keep it sorted

Binary search is only free if the data is already in order — and keeping data in order is real, ongoing work. Every time a library adds a book, a bank opens an account, or a school enrolls a student, something has to slot the new record into the right place.

Organizations pay that cost up front because they search the same data millions of times. Fast lookup isn’t magic; it’s preparation someone already did.

8

Connections

Came from 4.3 — same job as linear search, a completely different algorithm (4.1’s point).
Next in 4.5 — put the two step-count tables side by side. The gap is enormous.
Returns in 4.8 — binary search is guaranteed. Heuristics give that guarantee up on purpose.
Returns on the exam — “which list can binary search be used on?” and “how many elements are examined?” Sorted, and very few.
← 4.3 Linear Search