AP CSP Topic 3.11 Coding Practice - Binary Search

Big Idea 3: Algorithms and Programming · Topic 3.11 · Coding Practice

Binary Search — Code It Yourself

Write real code and check it against the expected output. Pick Python or JavaScript; the AP pseudocode reference is there when you need it.

You warmed these up on paper in the Trace the Shelf and Sorted or Not? exercises — same sorted shelf, now on screen. Type and run each one; they get harder as you go, ending with one you build from scratch. Everything here stays at the halving / iteration-count level: find the middle, eliminate half, count the checks. Predict the output first, then verify.

Problem 1 of 4

The shelf holds 15 books sorted by call number: [3, 8, 12, 15, 21, 26, 33, 40, 47, 52, 58, 61, 70, 75, 88]. Binary search always checks the MIDDLE book first. Print the value of that first middle book.

Expected output: 40

Show AP pseudocode reference
shelf ← [3, 8, 12, 15, 21, 26, 33, 40, 47, 52, 58, 61, 70, 75, 88]
middle ← (1 + LENGTH(shelf)) / 2
DISPLAY(shelf[middle])
For 15 items the middle is the 8th book (position 8 in the 1-indexed exam notation). In Python and JavaScript, lists are 0-indexed, so len(shelf) // 2 gives index 7 — the same middle book. Print the value stored there, not the index.

Problem 2 of 4

Count the WORST-CASE number of checks for the 15-book shelf. Start with 15 items and repeatedly halve the count (throwing away half each check) until nothing is left, counting each halving. Print the total number of checks.

Expected output: 4

Show AP pseudocode reference
size ← 15
checks ← 0
REPEAT UNTIL(size < 1)
{
  checks ← checks + 1
  size ← size / 2
}
DISPLAY(checks)
Halve with whole-number division so you count whole books: 15 → 7 → 3 → 1 → 0. That is 4 halvings, so 4 checks. Add 1 to checks each time BEFORE (or after) you halve — just make sure the loop stops when size hits 0.

Problem 3 of 4

Show the elimination. Starting from the 15-book shelf, print the number of books still in play AFTER each check (each check throws away half), one number per line, until none remain.

Expected output: 7 3 1 0

Show AP pseudocode reference
size ← 15
REPEAT UNTIL(size < 1)
{
  size ← size / 2
  DISPLAY(size)
}
Halve first, then print the new size: 15 halves to 7 (print 7), then 3, then 1, then 0 (print 0 and stop). The four numbers you print line up with the 4 checks from the previous problem.

Problem 4 of 4

Build it from scratch. A different library shelf holds 1000 books, sorted. Print the worst-case number of checks binary search needs to find a book — count how many times 1000 halves down to nothing.

Expected output: 10

Show AP pseudocode reference
size ← 1000
checks ← 0
REPEAT UNTIL(size < 1)
{
  checks ← checks + 1
  size ← size / 2
}
DISPLAY(checks)
Same halving loop as the 15-book shelf, just starting at 1000: 1000 → 500 → 250 → 125 → 62 → 31 → 15 → 7 → 3 → 1 → 0. Count the steps — 10. Linear search would need up to 1000 checks on the same shelf, which is the whole point.

Your code runs on a secure external service. Answers are checked automatically — nothing is stored.

Get in Touch

Whether you're a student, parent, or teacher — I'd love to hear from you.

Just want free AP CS resources?

Enter your email below and check the subscribe box — no message needed. Students get daily practice questions and study tips. Teachers get curriculum resources and teaching strategies.

Typically responds within 24 hours
✓

Message Sent!

Thanks for reaching out. I'll get back to you within 24 hours.

🏫 Welcome, fellow educator!

I offer curriculum resources, practice materials, and study guides designed for AP CS teachers. Let me know what you're looking for — whether it's classroom materials, a guest speaker, or Teachers Pay Teachers resources.

✉

Email

[email protected]

📚

Courses

AP CSA, CSP, & Cybersecurity

⏱

Response Time

Within 24 hours

Prefer email? Reach me directly at [email protected]