AP® Computer Science Principles review sheet from Aim for Five (aimforfive.com/csp/units/3/3-11)
Unit 3 · Topic 3.11
3.11 Binary Search
Binary search finds a value in a sorted list by repeatedly checking the middle and throwing away half of what's left. This topic covers how it works, why the list must be sorted, and how to count the most checks it can need compared with a linear search.
Key terms
- binary search
- sorted data
- linear search
- efficiency
How binary search works
Think of looking up a word in a dictionary. You don't start at page 1. You open to the middle, see whether your word comes before or after, and ignore the half it can't be in.
Binary search does the same with a sorted list:
- Check the middle element of the part of the list that's still possible.
- If it's the target, you're done.
- If the target is smaller, throw away the middle and everything after it. If it's larger, throw away the middle and everything before it.
- Repeat on the half that's left until you find the target or nothing is left.
It needs sorted data
Binary search only works if the data is in sorted order. Otherwise, the middle element tells you nothing about which half the target is in, and you could throw away the half that holds it.
Sorting a list takes time too. If you'll only search a list once, a linear search on the unsorted list can be the better choice. If you'll search it many times, sorting once and then using binary search pays off.
Why it's fast
Each check cuts the remaining list in half. A list of 1,000 elements becomes 500, 250, 125, 62, 31, 15, 7, 3 and then 1 element after 9 halvings, so binary search needs at most 10 checks.
To find the most checks for a list of n elements, count how many times you can halve n (dropping any remainder) before you reach 1, then add 1.
| List size | Linear search, most checks | Binary search, most checks |
|---|---|---|
| 16 | 16 | 5 |
| 128 | 128 | 8 |
| 1,000 | 1,000 | 10 |
| 1,000,000 | 1,000,000 | 20 |
Comparing it with linear search
Doubling the list size adds only one more check for binary search, but doubles the worst case for linear search. On large sorted lists, binary search is usually far more efficient.
On a small list, or when the target happens to be near the front, linear search can be just as quick. And linear search works on unsorted data, which binary search can't.
You won't be asked to write or trace a specific binary search program. You will need to explain how it works, why the data must be sorted, and roughly how many checks it needs.
Worked examples
Try each one yourself first, then open the solution.
- Example 1
Which elements get checked?
Binary search is used to look for 58 in this sorted list of 15 numbers: [3, 7, 12, 18, 21, 25, 30, 34, 41, 47, 52, 58, 63, 70, 77]. Which elements are checked, in order? (When the part left has two middle elements, use the one on the left.)
Show the solutionHide the solution
- Step 1: The whole list runs from position 1 to 15. The middle is position 8, which holds 34.
- Step 2: 58 > 34, so throw away positions 1 to 8. Positions 9 to 15 are left.
- Step 3: The middle of 9 to 15 is position 12, which holds 58. Found it.
- Step 4: Only 2 elements were checked. A linear search would have checked 12.
Answer: 34, then 58 (two checks).
- Example 2
Counting checks
A sorted list holds 128 names. What is the greatest number of names binary search has to check to find a name or decide it isn't there? What is it for a linear search?
Show the solutionHide the solution
- Step 1: Halve 128 until you reach 1: 64, 32, 16, 8, 4, 2, 1. That's 7 halvings.
- Step 2: Add 1 for the final check: 8.
- Step 3: A linear search could have to check every name: 128.
Answer: Binary search: at most 8. Linear search: up to 128.
Common mistakes
- Using binary search on an unsorted list. It can miss a value that's there.
- Saying binary search is always faster. For small lists, or a target near the start, linear search can be just as quick, and linear search is the only option for unsorted data.
- Counting halvings without adding the final check, giving an answer one too low.
On the exam
- Expect questions on the requirement (sorted data), on which search to use in a scenario, and on the maximum number of checks for a list of a given size.
- If an answer choice says binary search works on any list, it's wrong.
Connected topics
Videos
Check yourself
4 questions on 3.11 Binary Search. Pick an answer to see if you got it, and why.
On which list can a binary search be used to look for a value?
A binary search looks for 30 in the sorted list [3, 8, 12, 17, 21, 26, 30, 35, 40]. When the part of the list being searched has an even number of elements, the search checks the left one of the two middle elements. Which elements are checked, in order?
A sorted list contains 1,000 numbers. Using binary search, about how many elements, at most, must be checked to find a value or decide it isn't in the list?
A program needs to look up one name, once, in a list of 50,000 names that are in no particular order. Which search can be used, and why?
0 of 4 answered