AP Computer Science Principles · Unit 3 lecture · Part 10 of 14 · 8 min

3.11 Binary searchHalve it, halve it again

Mr. Thompkins
Pick a number from 1 to 1,000 and I'll guess it in 10 tries, if you tell me "higher" or "lower" each time. That trick is binary search, and it's one of the most powerful ideas in computing.

Binary search starts at the middle of a sorted data set and eliminates half of the data, based on whether the target is bigger or smaller than the middle element. It repeats this process on the remaining half until it finds the target or has eliminated every element. The data must be sorted for this to work: the whole trick depends on knowing that everything to the left of the middle is smaller.

4913182227313640445157637076491318222731364044515763707649131822273136404451576370764913182227313640445157637076orange: the middle checked. gray: ruled out
Binary search for 63 in a sorted list of 15 numbers. Four checks, and half (or more) of what's left is ruled out each time.
checklowhighmiddlevaluedecision
111583663 > 36: keep right
2915125763 > 57: keep right
31315147063 < 70: keep left
413131363found
The same search as a trace. One common way to pick the middle: (low + high) / 2, rounded down.
?Wait, why must the list be sorted?
Binary search throws away half the list based on one comparison with the middle. That's only safe if every smaller value is on one side and every larger value on the other. In an unsorted list, the target could be in the half you threw away.

How much faster is it? Each check cuts the remaining items roughly in half. Starting from n items, the number of checks in the worst case is about the number of times you can halve n before reaching 1, which is about log₂ n. For a million items, that's about 20 checks, against up to a million for linear search. Binary search is often far more efficient than linear search on sorted data. (The course doesn't test a specific way of coding binary search, only how it works and when it applies.)

Sorted itemsLinear search, worst caseBinary search, worst case
1515 checks4 checks
100100 checks7 checks
1,0001,000 checks10 checks
1,000,0001,000,000 checks20 checks
1,000,000,0001,000,000,000 checks30 checks
Worst-case checks. Linear search grows with n. Binary search grows by one check each time n doubles.
?Wait, how do I get the binary search number without logarithms?
Double until you pass n. 1, 2, 4, 8, 16: for 15 items, 4 doublings reach 16, so at most 4 checks. For 500 items: 2⁸ = 256 is too small, 2⁹ = 512 covers it, so at most 9 checks.
Pause and think
Your list has 1,000 items and you double it to 2,000. How many more checks does binary search need in the worst case? And linear search?
I thought about it. Show me
Binary search needs just one more check (about 11 instead of 10), since one extra halving handles the doubling. Linear search needs up to 1,000 more.
Run a binary search
Search the same sorted list for 5, which isn't in it. List each middle checked, and say how the search ends.
  1. Check 1: low 1, high 15, middle 8, value 36. 5 < 36, so keep the left half: high becomes 7.
  2. Check 2: low 1, high 7, middle 4, value 18. 5 < 18: high becomes 3.
  3. Check 3: low 1, high 3, middle 2, value 9. 5 < 9: high becomes 1.
  4. Check 4: low 1, high 1, middle 1, value 4. 5 > 4: low becomes 2. Now low is greater than high, so nothing is left: 5 is not in the list.
    Why?
    Even a failed search takes only about log₂ n checks. Linear search would have checked all 15.

Answer: Middles checked: 36, 18, 9, 4. After 4 checks every element is eliminated, so the search reports that 5 is not found.

Stuck? Get a hint
  1. Start with the middle of all 15: index 8.
  2. Each time 5 is smaller, keep only the left part.
  3. When the part left is empty, the value isn't there.
Check yourself
Which statement about binary search is true?
  1. AIt works on any list, sorted or not.
  2. BIt always checks every element.
  3. CIt requires sorted data and eliminates about half the remaining elements with each check.
  4. DIt is slower than linear search for large sorted lists.
Show the answer

C. Binary search needs sorted data and halves the search space each step, which makes it much faster than linear search on large sorted lists.

Check yourself
About how many checks does binary search need, at most, for a sorted list of 60,000 items?
  1. A16
  2. B30
  3. C245
  4. D60,000
Show the answer

A. 2¹⁵ = 32,768 is too small and 2¹⁶ = 65,536 covers 60,000, so at most 16 checks. 60,000 is the linear search worst case.

Exam tip from Mr. T

If a binary search question doesn't say the list is sorted, check that first. "The list is not sorted" makes every binary search answer wrong, and sorting it first might cost more than one linear search.

  • Binary search: check the middle of sorted data, eliminate half, repeat.
  • The data must be sorted. Linear search works on anything.
  • Worst case: about log₂ n checks. Doubling n adds one check.
  • On large sorted data, binary search is usually far more efficient than linear search.