AP CSP 3.11 Exercise 2: Binary Search Applied Challenge

Big Idea 3: Algorithms and Programming · Topic 3.11 · Exercise 2

Binary Search: Applied Challenge

Six questions on when binary search applies, and how few steps it actually needs.

Back to the Topic 3.11 lessonAll Big Idea 3 topics

How this one is different

The first thing the exam checks is whether you noticed the list was unsorted. The second is whether you can count halvings.

Applied Practice

6 questions · scenario driven · every answer is recorded for your teacher

Question 1 of 6Analyze
A student applies binary search to the list [9, 2, 7, 4, 1].
What is the problem?
Incorrect. Odd and even lengths are both fine.
Incorrect. Length is not the requirement, and five elements are plenty.
Correct. Discarding half the list is only valid if order guarantees the target cannot be in the discarded half. Without sorting, that guarantee is gone.
Incorrect. Any length works on a sorted list.
Question 2 of 6Apply
About how many comparisons does binary search need in the worst case on a sorted list of 1,000 elements?
Incorrect. 1,000 is the worst case for sequential search.
Correct. Each comparison halves the range, and roughly ten halvings reduce 1,000 to 1.
Incorrect. 100 would apply if each step removed a fixed tenth rather than half.
Incorrect. 500 is one halving, not the whole search.
Question 3 of 6Trace
Binary search runs on [2, 5, 8, 12, 16, 23, 38] looking for 23.
Which element is examined first, and which half survives?
Correct. The middle of seven elements is the fourth, which is 12. Since 23 is larger, everything at or below 12 is discarded.
Incorrect. The target is larger than the middle, so the left half is the half discarded.
Incorrect. The last element is not the starting point.
Incorrect. Binary search starts at the middle, not at the first element.
Question 4 of 6Evaluate
A list of 20 elements will be searched once, and it is unsorted.
Which approach is more sensible, and why?
Incorrect. Running binary search on unsorted data produces wrong answers regardless of size.
Incorrect. A 20 element list is trivially searchable.
Incorrect. Binary search is faster per search, but the sort has to be paid for first, and one search does not repay it.
Correct. The comparison is total work, not per search speed. Sorting to run a single search on a short list is a net loss.
Question 5 of 6Transfer
Doubling the size of a sorted list adds how many comparisons to a worst case binary search?
Incorrect. Nothing here squares. Squaring would mean the cost grew far faster than the list, which is the opposite of what halving does.
Incorrect. Doubling the comparisons is what happens to sequential search, not binary search.
Correct. One extra halving is enough to cut a doubled list back to the previous size, so the cost grows by about one step.
Incorrect. The cost does grow, just very slowly.
Question 6 of 6Apply
What must be true of a list before binary search will return correct results?
Incorrect. Any ordered data type works, including text.
Correct. Sorted order is the single prerequisite, because it is what makes discarding half the list safe.
Incorrect. Element count parity is irrelevant.
Incorrect. Duplicates are fine. The search still finds a matching value.

Where to go next

Rework the Topic 3.11 lesson and quiz Sit the Big Idea 3 unit test part A Sit the Big Idea 3 unit test part B

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]