Binary Search: Study Guide (Computer Science Principles 3.11)

Imagine looking for a name in a printed phone book. You do not start at page 1 and read every name; you open the book near the middle, see whether your name comes before or after that page, and throw away the half you do not need. Then you repeat on the half that is left. Binary search is exactly this strategy turned into an algorithm, and it is dramatically faster than checking every item when the data is large. This topic explains how binary search works, why the data must be sorted, and how to work out the greatest number of checks it needs.

Notation. The exam uses its own pseudocode, not a real programming language. The code in this pack is Marlbridge’s rendering of that reference notation, not a copy of the official sheet: ← is assignment, = tests equality, lists start at index 1, DISPLAY shows a value, and braces mark blocks. Use the Exam Reference Sheet from your teacher for the official wording.

Scope. The course expects you to understand the idea and to work out the number of iterations. Specific implementations of binary search are outside the course and the exam. The code in this guide is an illustration to help you see the process, and it uses a procedure (see Topic 3.12).

How binary search works

Binary search finds a target value in a sorted list. The steps are:

1. Look at the middle element of the part of the list still under consideration.
2. If it equals the target, you are done.
3. If the target is smaller than the middle element, every element at or above the middle is too big: eliminate that half, keeping the lower part.
4. If the target is larger, eliminate the lower half, keeping the upper part.
5. Repeat on the remaining half until the target is found or no elements remain.

Each check removes about half of what is left. That is why it is so fast: after 10 checks a list of 1,000 values has been narrowed to a single candidate.

Why the data must be sorted. Step 3 is only valid because in a sorted list everything above the middle element is at least as big. If the data is in no order, throwing away half the list may throw away the target. So the exam fact is simple: binary search requires the data to be in sorted order. Linear search has no such requirement.

Worked example 1: trace a successful search

The sorted list DATA is [3, 8, 12, 15, 21, 26, 30, 34, 41, 47, 52, 58, 63, 71, 79], fifteen values at positions 1 to 15. Trace a binary search for 52 (Figure 1 shows the same trace).

Check	Live positions	Middle position	Value there	Compare with 52	Action
1	1–15	8	34	34 < 52	Keep the upper half (9–15)
2	9–15	12	58	58 > 52	Keep the lower half (9–11)
3	9–11	10	47	47 < 52	Keep the upper part (11)
4	11–11	11	52	52 = 52	Found at position 11

Check. Four checks examined only four of the fifteen values. A linear search for 52 would have examined 11 (every value from the start up to position 11).

For the illustration, here is a version in code that also counts the checks. It returns a two-element list: the position (0 if not found) and the number of checks. Do not memorise it; use it to run your own experiments.

PROCEDURE binarySearch(aList, target)
{
  low ← 1
  high ← LENGTH(aList)
  checks ← 0
  REPEAT UNTIL(low > high)
  {
    middle ← (low + high - (low + high) MOD 2) / 2
    checks ← checks + 1
    IF(aList[middle] = target)
    {
      RETURN([middle, checks])
    }
    IF(aList[middle] < target)
    {
      low ← middle + 1
    }
    ELSE
    {
      high ← middle - 1
    }
  }
  RETURN([0, checks])
}

For example, binarySearch(DATA, 52) gives position 11 after 4 checks, and binarySearch(DATA, 30) gives position 7 after 4 checks, as the program confirmed when we ran it.

Worked example 2: how many checks, and why sortedness matters

Part A. The maximum number of checks. Each check at least halves the list. So the greatest number of checks is the number of times you can halve the list size until one candidate remains, plus the final check of that candidate. As a rule: the maximum number of checks for a list of n items is the smallest k such that 2^k − 1 ≥ n, which is the same as ⌊log₂ n⌋ + 1. You do not need logarithms in the exam; you can find k by doubling 1, 2, 4, 8, … until the doubled value passes n. For 1,000 items:

1,000 → 500 → 250 → 125 → 62 → 31 → 15 → 7 → 3 → 1.

That is nine halvings, plus checking the last remaining item: 10 checks. Another way: 2¹⁰ = 1,024 is the first power of two that is more than 1,000, so 10 checks are enough, and 2⁹ = 512 is too small.

Items in the list n	Greatest checks, binary search	Greatest checks, linear search
15	4	15
100	7	100
1,000	10	1,000
5,000	13	5,000
1,000,000	20	1,000,000

Notice what happens when the list doubles: binary search needs only one more check, while linear search needs twice as many. That is the key advantage on large data.

Check. The table values agree with a program check that ran binary search on every possible target in every list length up to 3,000 and recorded the worst case, and with the doubling rule for the larger sizes. Binary search is “often more efficient” than linear search on sorted data. It is not always faster: if the target is the first item, a linear search needs one check.

Part B. What goes wrong with unsorted data. Search for 5 in [9, 2, 14, 5, 11], which is not sorted. The middle value is 14 (position 3). Since 5 < 14, binary search discards positions 3 to 5, including the 5 itself. It next looks at the lower half, [9, 2], finds the middle value 9 and then 2, and reports not found, even though 5 is in the list. This was confirmed by running the code above, which returns position 0.

Binary search therefore gives wrong answers on unsorted data. If the data is unsorted, either use linear search or sort it first.

Choosing between linear and binary search

• Data unsorted, searched once: use linear search. Binary search is not allowed because the data is not sorted.
• Data sorted, large, searched many times: use binary search. It saves a great deal of work.
• Data sorted but tiny: the difference is small; choose the simpler method.
• Data keeps changing: keeping it sorted costs effort, which may or may not be worth it. (Sorting algorithms are not part of this course.)

Common misconceptions

• “Binary search works on any list.” It needs the data in sorted order.
• “Binary search always finds the target faster than linear search.” Linear search can be quicker if the target happens to be near the front. Binary search is better in the worst case and on average for large data.
• “The number of checks is half the list size.” It is the number of times you can halve the list: 10 for 1,000 items, not 500.
• “Binary search looks at the first element first.” It starts at the middle.
• “After a check you keep the half with the middle value.” The middle value has already been compared; it is eliminated along with the wrong half.
• “Doubling the list size doubles the checks.” For binary search it adds only one check.

Where this leads

Binary search is your first example of an algorithm whose cost grows slowly as the data grows. Topic 3.17 builds on this idea by comparing algorithms by how many steps they take as the input gets bigger.

Next steps: try the practice questions, skim the revision notes the night before, and tick off the topic checklist. The next topic is Topic 3.12, Calling Procedures.