AP CSP Binary Search
AP CSP Binary Search: Complete Guide (2025‑2026)
Binary search finds a target in a sorted list by repeatedly halving the search space. It checks the middle element: if it matches, done; if the target is larger, search the right half; if smaller, search the left half. This divide-and-conquer approach reduces a 1,000-element list to at most 10 comparisons. The critical requirement: the list must be sorted. Binary search on an unsorted list produces wrong answers with no error.
Contents
How Binary Search Works
Each step eliminates half the remaining candidates. 8 elements, 3 steps. 1,000 elements, 10 steps. 1,000,000 elements, 20 steps.
Binary vs. Linear Search
- Requires sorted list — always
- log2(N) max comparisons: 1M elements = 20 steps
- Middle element drives direction
- Finding vs. not-found both fast
- Harder to implement correctly
- Works on sorted OR unsorted lists
- N max comparisons: 1M elements = 1M steps
- Every element checked in order
- Simple to implement and verify
- Required when list cannot be sorted
Code Trace Gauntlet
How many comparisons to find 7 in [1,3,5,7,9,11,13]?
1 comparison Mid index = (1+7)/2 = 4. lst[4] = 7 = target. Found immediately in 1 comparison — best case.
How many comparisons to find 25?
3 comparisons Each step eliminates the half where 25 cannot be.
3 comparisons before concluding 4 is not in the list. What makes binary search return false?
false When low > high, the search space is empty — the target cannot be in the remaining range. Binary search terminates with false after 3 steps instead of checking all 5 elements.
How many comparisons does binary search need for a 1,024-element list in the worst case?
10 comparisons log2(1024) = 10. Each step halves the search space. 1024→512→256→128→64→32→16→8→4→2→1. 10 steps.
Spot the Bug
Binary search on an unsorted list can miss the target entirely. The algorithm assumes sorted order to decide which half to search. Without sorting, this assumption is violated and results are incorrect. Always sort before binary search.
Operator precedence: division runs before addition. low + high / 2 computes high/2 first. Fix: (low + high) / 2 with parentheses. Always parenthesize the sum when computing the midpoint.
Common Exam Pitfalls
This is the most-tested binary search fact. Applying binary search to an unsorted list produces wrong results with no error message.
Not half the total list — half of what remains. After step 1 on 8 elements, 4 remain. After step 2, 2 remain.
16 elements: max 4 comparisons (log2(16)=4). N/2 would be 8. These are very different.
If the target is always at the midpoint, binary search finds it immediately. Best case = 1.
Check for Understanding
1. Binary search requires that the list be:
- Stored in a hash table
- Sorted in ascending or descending order
- Free of duplicate values
- Stored in contiguous memory
2. A sorted list has 32 elements. What is the maximum number of comparisons binary search needs?
- 4
- 5
- 16
- 32
3. In binary search, if the middle element is less than the target, what happens next?
- Search the left half (lower values)
- Search the right half (higher values)
- The search ends (target not found)
- Start over from the beginning
4. A student applies binary search to an unsorted list. What is the most likely outcome?
- A runtime error occurs
- The search always returns false
- The search may miss the target and return an incorrect result
- The search sorts the list automatically before searching
5. Consider: I. Binary search works on sorted lists only. II. Binary search always requires fewer comparisons than linear search. III. Binary search halves the search space with each comparison.
- I and III only
- I only
- I, II, and III
- II and III only
6. Binary search on a sorted list of 1,000,000 elements makes at most how many comparisons?
- 500,000
- 1,000
- 20
- 100
7. lst ← [1,3,5,7,9,11,13,15]
Target: 1
Binary search starts at the middle element (index 4, value 7). 1 < 7, so it searches the left half. In the left half [1,3,5,7], mid is index 2, value 3. 1 < 3, so it searches [1]. How many total comparisons?
- 1
- 2
- 3
- 4
8. Why is binary search not always preferable to linear search?
- Binary search is slower for all list sizes.
- Binary search requires a sorted list, and sorting itself takes time and effort.
- Binary search uses more memory than linear search.
- Binary search can only search for numbers, not strings.
9. A sorted list of 8 elements. Binary search for a value that is NOT in the list. What is the maximum number of comparisons?
- 3
- 4
- 8
- 2
10. Which statement correctly describes the efficiency advantage of binary search?
- Binary search is twice as fast as linear search.
- Binary search makes at most log2(N) comparisons, while linear search may require N.
- Binary search eliminates all comparisons after the first step.
- Binary search is faster because it reads elements from right to left.
How the AP Exam Tests This
- Determine whether binary search or linear search is appropriate for a given list
- Calculate the maximum number of comparisons for a given list length (log2(N))
- Trace binary search steps on a small sorted list
- Identify that binary search on an unsorted list produces incorrect results
- I/II/III: which statements about binary search are correct
FAQ
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.
Message Sent!
Thanks for reaching out. I'll get back to you within 24 hours.
tanner@apcsexamprep.com
Courses
AP CSA, CSP, & Cybersecurity
Response Time
Within 24 hours
Prefer email? Reach me directly at tanner@apcsexamprep.com