Searching and sorting
Computer Science · GCSE · The School
Two ways to find
LINEAR search checks items one by one from the start — works on any list, slow on big ones (up to n checks for n items). BINARY search needs a SORTED list: check the middle, discard the half that cannot contain the target, repeat. Each step halves the problem — a million items need at most ~20 checks. Sorted-ness is the price of that speed.
Bubble sort, honestly slow
Bubble sort walks the list comparing neighbours and swapping when out of order; each full pass "bubbles" the largest remaining value to the end. [5,3,8,2]: pass 1 → [3,5,2,8]; pass 2 → [3,2,5,8]; pass 3 → [2,3,5,8]. Easy to write and trace, painful at scale — its comparisons grow with n², so doubling the list quadruples the work.
Why efficiency matters
For 10 items, nothing matters. For 10 million — a search engine, a game leaderboard — the difference between n and log(n), or n² and n·log(n), is the difference between instant and unusable. GCSE asks you to compare algorithms in exactly these terms: how does the work grow as the input grows?
Start: 5, 3, 8, 1. Compare 5 and 3 — swap: 3, 5, 8, 1. Compare 5 and 8 — no swap. Compare 8 and 1 — swap: 3, 5, 1, 8. End of pass one, and the largest value has bubbled to the end, which is guaranteed after every pass. Pass two: 3, 5, 1, 8 → 3, 1, 5, 8. Pass three: 1, 3, 5, 8. Sorted. Note that the number of comparisons grows with the SQUARE of the list length — which is why it is not used on real data.
Binary search, traced step by step
Search for 23 in [2, 5, 8, 12, 16, 23, 30, 41, 55]. Nine items, so start at the middle, index 4 (value 16). 23 is bigger, so the whole left half is discarded, leaving [23, 30, 41, 55]. Its middle is 30. 23 is smaller, so the right half goes, leaving just [23]. Check it — found, in three comparisons rather than the six a linear scan of nine items could need. Each comparison throws away half of what is left, which is exactly why the count grows so slowly as the list grows.
Binary search has a precondition
It only works on sorted data, and forgetting that is a common lost mark. So the real comparison is not "binary beats linear" but "does the list stay sorted, and how often do you search it?" Sorting once and searching a thousand times is worth it; sorting to search once is not.