Print these notesAll CSP topics

01. How Binary Search Works — Halve and Count

Key Vocabulary (LO AAP-2.P)

Term	Definition (write it)
Binary search
Sorted data
Iteration
Eliminate half
More efficient

Start in the Middle, Eliminate Half

• Instead of scanning one element at a time, each step of binary search .
• It decides which half to discard by comparing the target to the value sitting at .
• For this topic the exam expects the halving idea and iteration count rather than .

Trace a Search, Count the Iterations

A shelf holds 15 books sorted by call number: [3, 8, 12, 15, 21, 26, 33, 40, 47, 52, 58, 61, 70, 75, 88]. We search for book 21 (position 5). Each iteration checks the middle of the region in play, then eliminates the half that cannot hold it. Middle position = (low + high) / 2, rounded down. Fill in the blanks, then count the iterations.

Complete the empty cells.

Iteration	Region (positions in play)	Middle position checked	Value there vs target 21	Half eliminated
1	1–15	8	40 > 21	positions 8–15 (the larger half)
2	1–7		15 < 21	positions 1–4 (the smaller half)
3	5–7		26 > 21	positions 6–7 (the larger half)
4	5–5	5		— (value found)

Halve the Count Until Nothing Is Left

Halving the number of items still in play: a 15-item shelf needs at most 4 checks — the same 4 iterations we just traced.

AP Pseudocode (what the exam tests)

itemsLeft ← 15
checks ← 0
REPEAT UNTIL(itemsLeft < 1)
{
  checks ← checks + 1
  itemsLeft ← itemsLeft / 2
}
DISPLAY(checks)

Python (the runnable version)

items_left = 15
checks = 0
while items_left >= 1:
    checks = checks + 1
    items_left = items_left // 2
print(checks)

Output

4

Run and edit this yourself in the coding exercises for this topic.

02. The Sorted Requirement and Why It Wins

The One Rule: The Data Must Be Sorted

• Binary search cannot run correctly unless the data set is .
• Sorting matters because it guarantees that one side of the middle holds only .
• On unsorted data, eliminating a half is unsafe because it can discard .

Linear Search vs Binary Search

Linear (sequential) search

Binary search

• On a sorted list of 1000 items, linear search may need up to 1000 checks, while binary search needs only about .
• Binary search is often more efficient than linear search, but only when the data is .

The Payoff, in Numbers

Worst-case number of checks for each search as the list grows. Linear search's worst case is n (check them all); binary search's worst case is the number of times n halves down to nothing. Fill in the blanks by halving.

Complete the empty cells.

List size (n)	Linear search — worst-case checks	Binary search — worst-case checks
7	7	3
15	15
100	100
1000		10

Common AP Traps

Three ways Topic 3.11 loses points on the exam — one minute now, real points in May.

Binary search REQUIRES sorted data — in your own words:

Count halvings, not elements — in your own words:

You are tested on the IDEA, not an implementation — in your own words:

Binary Search, in One Slide

• Binary search starts at the MIDDLE of a sorted data set and eliminates half of the data each step, repeating until the value is found or all elements are eliminated.
• Count iterations by halving the size down to nothing — 15 → 7 → 3 → 1 → 0 is 4 checks; doubling the data adds just one iteration.
• The data MUST be in sorted order; the eliminate-half decision is only valid when one side of the middle is smaller and the other larger.
• On sorted data binary search is often far more efficient than linear search — about 10 checks for 1000 items versus up to 1000.