Comparing and Selecting Searching Algorithms

AQA 4.3.4 — Selecting a searching algorithm

Retrieval: this lesson deliberately doesn't teach a new searching algorithm — it retrieves and compares three you already know in full depth: Year 12's Linear Search and Binary Search, and Sequence 12's Binary Search Tree search. The skill this lesson builds is genuinely different from implementation: selecting the right strategy, and rejecting the wrong ones, for a given scenario.

Understand — three genuinely different strategies, now fully known

• Linear Search — check every element in turn. O(n). Works on any data, sorted or not.
• Binary Search — repeatedly halve a sorted array by comparing to the middle. O(log n). Requires the data to already be sorted, and re-sorting after every change has its own cost.
• BST search — follow left/right links guided by the BST property. O(log n) average (Sequence 12's Analyse section: O(n) worst case if unbalanced). Requires a pre-built tree, but stays efficient even as data changes, unlike a sorted array.

See it — the comparison, side by side

Reason about correctness — why Binary Search produces incorrect results on unsorted data

Binary search's entire correctness depends on a single assumption: that comparing the target to the middle element genuinely tells you which half the target could be in. If the array isn't actually sorted, that assumption is false — the target could be on either side of the middle regardless of the comparison result, so eliminating a half based on that comparison can silently discard the half the target was actually in. The algorithm doesn't crash; it simply returns a wrong "not found" result, or finds the wrong index, with no indication anything went wrong at all.

Debug it — diagnose, explain, fix, test, justify (algorithm/data-structure mismatch)

scores = [55, 62, 71, 68, 90]   # NOT sorted - 68 is out of order

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

print(binary_search(scores, 68))

This returns -1 ("not found") even though 68 is genuinely present in the list at index 3.

1. Diagnose: is scores actually sorted in ascending order?
2. Explain: using the correctness reasoning above, why does searching for 68 fail even though it's clearly in the list?
3. Fix: propose a correct fix.
4. Test: confirm the fixed version correctly locates 68.
5. Justify: explain why this bug is more dangerous than a crash — what does the program's behaviour look like to someone who doesn't already know the answer?

(scores is not sorted (68 appears after 71, which is larger). Binary search's halving logic assumes sorted data; on this input, the comparison at mid eliminates the wrong half, silently skipping over 68. A correct fix either sorts the list first (sorted(scores)) before searching, or uses linear search instead, which makes no sorted-data assumption at all. This is more dangerous than a crash because the program returns a plausible, confidently-wrong answer - "not found" - with no indication that anything went wrong, exactly the "algorithm/data-structure mismatch" class of bug introduced in Sequence 12.)

Common mistake

Treating "requires sorted data" as a minor implementation detail rather than a genuine precondition for correctness. As the Debug it task shows, running binary search on unsorted data isn't merely slower or clumsier — it's simply wrong.

Select, justify, reject — three scenarios

1. A phone book app needs to search an unsorted list of 10 million contacts, once, for a single lookup that will never be repeated. Select an appropriate algorithm.
2. A leaderboard of exactly 20 players, resorted after every single game, needs frequent lookups by player name between resorts.
3. A colleague proposes using binary search to find a name in an unsorted guest list of 50 names. Reject this proposal and justify a better choice.

(1: Linear search - with only one lookup ever needed, sorting 10 million contacts purely to enable one binary search would cost far more than the single linear scan it's meant to avoid. 2: Binary search on the freshly-sorted list is reasonable at this small, frequently-resorted scale, though the resorting cost is a genuine trade-off worth naming. 3: Reject binary search - the guest list isn't sorted, so (per the correctness reasoning above) binary search would risk returning an incorrect "not found" result for a name that's genuinely present; linear search, which makes no sorted-data assumption, is the appropriate and safe choice here.)

Check your understanding

A colleague proposes using Binary Search Tree search instead of Linear Search for a list of exactly 6 items that is searched only once and never reused. Evaluate this proposal. (3 marks)

(Not appropriate. Building a BST at all requires inserting every item first - genuine setup cost - and for only 6 items searched once, the difference between O(n) and O(log n) is negligible (6 vs. roughly 3 comparisons). The setup cost of building a tree that will only be used for a single search isn't justified here; linear search on the plain list is simpler and just as fast in practice at this scale.)

Challenge

A dictionary app stores 500,000 words, needs extremely fast lookups, and rarely adds new words after initial loading. Propose and justify a searching strategy, explicitly rejecting at least one alternative.

Looking ahead: the next lesson introduces a genuinely new algorithm — merge sort — extending the divide-and-conquer thinking behind binary search's halving strategy to sorting an entire list, not just finding one item within it.