3.11 Binary Search

What you need to know

• Binary search requires the list to be sorted. On unsorted data it doesn't work at all. This is the single most-tested fact.
• Procedure: look at the middle element. If it's the target, done. If the target is smaller, discard the upper half; if larger, discard the lower half. Repeat on the remaining half.
• Each step halves the number of elements left to check. A list of 1,000 elements takes at most about 10 checks (2¹⁰ = 1,024); a million takes about 20.
• Linear search checks elements one at a time and may need to check every element — up to n checks for n items.
• The exam asks: given a sorted list of N items, what's the maximum number of checks binary search needs? Answer: the smallest k where 2^k > N. For 15 items that's 4 (2⁴ = 16 > 15); for 64 items it's 7 (2⁷ = 128 > 64). Roughly log₂ N, rounded down, plus one for the final check.
• Binary search is a selection + iteration algorithm: repeated comparison and narrowing.
• Trade-off: sorting has a cost. If you only search once, sorting then binary searching may not beat a single linear search. If you search many times, sort first.

Worked example

Sorted list: [2, 5, 9, 14, 21, 30, 44, 51, 63], target 44.

1. Middle (index 5) is 21. 44 > 21 → keep the right half: [30, 44, 51, 63].
2. Middle is 44 (or 51 depending on rounding; either way one more step). Found at step 2 or 3.

Linear search would have needed 7 checks to reach 44. With 9 elements, binary search never needs more than 4 (2⁴ = 16 ≥ 9).

Going deeper

The nuance, edge cases, and connections that turn a 3 into a 5.

• Why sorted is required: binary search decides which half to discard by comparing the middle element to the target. That decision is only valid if smaller values are all on one side and larger on the other — i.e., if the list is sorted. On unsorted data, the target could be in the discarded half.
• The maximum number of comparisons for n elements is the smallest k such that 2^k > n. This equals ⌊log₂ n⌋ + 1. Table: n = 7 → 3; n = 8 → 4; n = 15 → 4; n = 16 → 5; n = 100 → 7; n = 1000 → 10; n = 1,000,000 → 20.
• A question may give the actual list and target and ask which elements are examined. Trace it: middle first, then the middle of the remaining half, until found. Different rounding conventions for the middle (floor vs. ceiling) can change the exact elements; the exam usually specifies or uses a list where it doesn't matter.
• Linear vs. binary trade-off: linear needs no preparation but takes up to n steps. Binary needs a sorted list (sorting costs time) but takes log n steps. For one search on an unsorted list, linear wins. For many searches, sort once and use binary.
• Binary search is a selection + iteration algorithm: each iteration selects a half. Its efficiency is logarithmic, which the CED classifies as reasonable time — and it's the exam's main example of an algorithm that scales dramatically better than linear.
• Binary search generalizes: guessing a number between 1 and 1000 by always guessing the middle takes at most 10 guesses. Same algorithm, same log₂ bound.

Mistakes that cost points

• Applying binary search to an unsorted list. If the stem doesn't say sorted, binary search isn't valid. That's frequently the entire question.
• Off-by-one on the step count. For n = 16, students say 4 (log₂ 16). The maximum is 5, because after four halvings you have one element left and still have to check it. Use "smallest 2^k greater than n."
• Assuming binary search is always better. If the list is unsorted and you search once, linear search is faster than sorting-then-binary.

Practice questions

Written in the style of the real exam. Try each one before revealing the answer.