Searching algorithms

What you need to know

• ✓Linear search inspects every item one by one from the start of the list until the target is found or the end of the list is reached.
• ✓Linear search works on both unordered (unsorted) and ordered (sorted) datasets.
• ✓Binary search repeatedly halves the search space by comparing the target with the middle item. If the target is smaller, the upper half is discarded; if larger, the lower half is discarded.
• ✓Binary search requires the dataset to be in sorted order before searching can begin.
• ✓Binary search is significantly more time-efficient than linear search on large lists because each comparison halves the remaining items.
• ✓If a list is unsorted and you only need to search it once, linear search is usually faster than sorting the entire list first just to run a binary search.

What you don’t need

• Formal Big-O notation (e.g. O(n) or O(log n)) — AQA GCSE questions refer only to time efficiency in plain words.
• Space complexity and memory comparisons between searching algorithms.
• Writing binary search in program code from scratch — the specification tests tracing and explaining the algorithm.

Worked examples

1. A list contains the numbers [3, 7, 11, 15, 19, 23, 27]. Trace a binary search to find the number 19, showing the list or midpoint at each step.

   1. Step 1: Identify the middle item of the 7-item list. The midpoint is 15 (index 3).
   2. Step 2: Compare 19 with 15. Since 19 > 15, discard the lower half [3, 7, 11, 15]. The remaining sublist is [19, 23, 27].
   3. Step 3: Find the middle of [19, 23, 27], which is 23.
   4. Step 4: Compare 19 with 23. Since 19 < 23, discard the upper half [23, 27]. The remaining sublist is [19].
   5. Step 5: The middle item is 19. It matches the target, so the search terminates with success.

   Answer: Target 19 found in 3 comparisons (examined 15, then 23, then 19).

2. Give one advantage and one disadvantage of a binary search compared with a linear search. (2 marks)

   Answer: Advantage: Much faster / more time-efficient on large lists because it halves the remaining items on each step. Disadvantage: The list must already be sorted before the search can start.

Common mistakes

• ✕Applying binary search to an unsorted list. Binary search relies on order to discard halves; on an unsorted list it may discard the half holding the target.
• ✕Counting all items when calculating binary search steps instead of halving the search space.
• ✕Confusing linear search with binary search in efficiency questions — linear search checks up to n items; binary search checks roughly 10 times for 1,000 items.
• ✕Stating that binary search is always faster than linear search. If the target is the very first item in the list, linear search finds it in 1 check, whereas binary search checks the middle item first.