Binary Search (College Board AP® Computer Science Principles): Revision Note
Binary search fundamentals
What is a binary search?
A binary search is an algorithm for finding a value in a sorted data set
The algorithm starts at the middle of the sorted data set and eliminates half of the data at each step
This process repeats until the desired value is found or all elements have been eliminated
Because half of the remaining data is discarded at each step, binary search can find a value very quickly even in large data sets
Requirements for a binary search
The data must be in sorted order to use binary search
If the data is not sorted, the algorithm cannot correctly decide which half of the data to eliminate, and may fail to find a value that is actually present
If the data is unsorted, it must either be sorted first, or a linear search must be used instead
Binary search efficiency
How does binary search compare to linear search?
A linear search checks each element of a list in order, until the desired value is found or all elements have been checked
A binary search eliminates half of the remaining data at each step, so it usually needs far fewer comparisons than a linear search on the same sorted data
Binary search is often more efficient than sequential or linear search when applied to sorted data
Approximate iteration counts
In a list of 8 elements, a binary search needs at most about 3 iterations
In a list of 1,000 elements, a binary search needs at most about 10 iterations
In a list of 1,000,000 elements, a binary search needs at most about 20 iterations
By contrast, a linear search on the same lists would need up to 8, 1,000, and 1,000,000 comparisons in the worst case
Search algorithm | Maximum comparisons (1,000 items) | Requires sorted data |
|---|---|---|
Linear search | 1,000 | No |
Binary search | About 10 | Yes |
Examiner Tips and Tricks
In AP exam questions, the first thing to check is whether the data is sorted. If it is not sorted, binary search is not a valid answer — linear search is the only option.
Binary search questions on the AP exam typically ask for the maximum number of iterations needed to find a value, not for a trace of which specific elements are compared. Because each iteration halves the data, the maximum number of iterations grows very slowly as the size of the data set grows.
For the AP Create Performance Task, if your program searches a sorted list, using binary search demonstrates an understanding of algorithmic efficiency that you can discuss in your written response — in particular, that binary search is often more efficient than linear search on sorted data.
Worked Example
A sorted list contains 500 numbers. A binary search is used to find a particular value in the list.
Which of the following is closest to the maximum number of list elements that will be examined during the search?
(A) 10
(B) 50
(C) 250
(D) 500
[1]
Answer:
(A) 10 [1 mark]
Each iteration of a binary search eliminates half of the remaining elements. Starting with 500 elements, the size of the portion still being searched roughly halves each iteration — 500, 250, 125, 63, 32, 16, 8, 4, 2, 1 — so the target will be found (or ruled out) within about 10 iterations. This is far fewer than the 500 comparisons a linear search would need in the worst case.
Unlock more, it's free!
Join the 100,000+ Students that ❤️ Save My Exams
the (exam) results speak for themselves:
Was this revision note helpful?
