Searching and sorting algorithms
Computer Science · Key Stage 3 · The School
Two ways to search
LINEAR SEARCH checks each item in turn until it finds the target. It works on any list, and on average checks half of it. BINARY SEARCH jumps to the middle, discards the half that cannot contain the target, and repeats — but it only works on a SORTED list, because discarding a half depends on knowing which side the target must be on.
How much better
On a list of a thousand items, linear search takes about five hundred checks on average. Binary search takes about ten, because each step halves what is left. On a million items it is about five hundred thousand against twenty. That gap is why sorting data first is often worth the effort even though sorting itself costs time.
Comparing algorithms
Algorithms are compared by how the work GROWS as the data grows, not by how fast they run on one machine. Doubling the list roughly doubles a linear search but adds only one step to a binary search. Timing a program tells you about your computer; counting the steps tells you about the algorithm.
LINEAR search checks every item until it finds the target: up to 1,000,000 checks. BINARY search halves the list each time: 1,000,000 → 500,000 → 250,000 … which reaches one item in about 20 steps. But binary search REQUIRES sorted data, and sorting a million items costs far more than one linear scan. So: searching once in unsorted data, linear wins. Searching repeatedly, sort first and use binary.