Efficiency and Searching Algorithms
What efficiency actually means for an algorithm, how linear and binary search work step by step, and the exact conditions under which each one is the right choice.
What efficiency means
Two algorithms can produce exactly the same correct answer and still be worlds apart in usefulness. The efficiency of an algorithm is how much of a resource it consumes to get that answer, and at GCSE the resource that matters is the number of steps, which translates into time.
The reason this is worth measuring is that the difference between algorithms grows with the size of the data. On ten items nothing matters. On ten million items the choice of algorithm decides whether a program is instant or unusable.
Count the number of comparisons each algorithm makes on the same data, in the worst case. The one that makes fewer comparisons as the list grows is the more efficient algorithm.
Worst case, best case
- Best case is the luckiest possible input. For linear search that is the item being first.
- Worst case is the least lucky input. For linear search that is the item being last, or absent altogether.
Examiners nearly always ask about the worst case, because the best case is a matter of luck and tells you nothing useful about the algorithm.
The point that earns the mark
A faster algorithm does not need faster hardware. Changing from linear search to binary search on a large sorted list makes a program dramatically quicker on exactly the same machine, because it does less work rather than doing the same work faster. That is the sentence to write when a question asks why algorithm choice matters.
Linear search
A linear search starts at the beginning of the list and compares each item in turn with the value being looked for, stopping when it finds a match or when it reaches the end of the list.
SUBROUTINE linearSearch(items, target)
FOR i ← 0 TO LEN(items) - 1
IF items[i] = target THEN
RETURN i
ENDIF
ENDFOR
RETURN -1
ENDSUBROUTINESearching for 23 in [4, 8, 15, 16, 23, 42] compares 4, then 8, then 15, then 16, then 23. Five comparisons, then it stops.
The properties that matter
- The list does not have to be sorted. This is linear search's one real advantage and it is a big one.
- The worst case is n comparisons on a list of n items, when the target is last or missing.
- It is simple to write and hard to get wrong.
When the data is unsorted, when the list is short, or when the list changes so often that keeping it sorted would cost more than the searches save.
- Linear search looks at every item in turn from the start, so it can be slow.
- Binary search checks the middle and throws half the list away each time.
- 3 looks against 10. The longer the list, the bigger the gap, but binary search needs the list sorted.
Binary search
A binary search works on a sorted list. It compares the target with the middle item, and then discards half the list.
- Find the middle item of the list.
- If it is the target, stop.
- If the target is smaller than the middle item, repeat using only the left half.
- If the target is larger, repeat using only the right half.
- If there are no items left to check, the target is not in the list.
Traced on a real list
Searching for 23 in the sorted list [4, 8, 15, 16, 23, 42]:
| Step | List being searched | Middle item | Comparison | Action |
|---|---|---|---|---|
| 1 | 4, 8, 15, 16, 23, 42 | 15 | 23 is greater than 15 | Keep the right half: 16, 23, 42 |
| 2 | 16, 23, 42 | 23 | 23 equals 23 | Found, stop |
Two comparisons instead of five. On six items that is barely worth mentioning. The reason binary search matters is what happens as the list grows.
| Items in list | Linear search, worst case | Binary search, worst case |
|---|---|---|
| 100 | 100 | 7 |
| 1 000 | 1 000 | 10 |
| 1 000 000 | 1 000 000 | 20 |
| 1 000 000 000 | 1 000 000 000 | 30 |
Every time the list doubles, binary search needs just one extra comparison, because one extra comparison halves the list one more time. Linear search needs twice as many.
This is the condition examiners test. If a question describes data arriving in a random order and never being sorted, binary search is not available, however efficient it would be.
Ask two questions of the scenario. Is the data sorted? How big is it? Sorted and large means binary. Unsorted, or so small that sorting would cost more than searching, means linear. Say which condition in the scenario made you choose, because that is where the mark is.
The hidden cost
If the data is not already sorted, binary search is only worth it when you will search many times. Sorting a list takes considerably more work than one linear search, so sorting purely to run a single binary search is slower overall than just doing the linear search.
Key terms you must be able to define
- Efficiency
- A measure of how much of a resource, usually time or number of steps, an algorithm uses to solve a problem.
- Linear search
- A search that examines each item in a list in turn until the target is found or the end of the list is reached.
- Binary search
- A search on a sorted list that repeatedly compares the target with the middle item and discards the half that cannot contain it.
- Worst case
- The input that causes an algorithm to perform the greatest number of steps.
- Comparison
- One test of whether an item matches or is greater or less than the value being searched for, used as the unit for measuring search efficiency.
- Sorted list
- A list whose items are in ascending or descending order, which is the condition binary search requires.
- Middle item
- The item at the centre of the section of the list currently being searched by a binary search.
Flashcards
Say the definition out loud before you flip the card. Retrieving it from memory is what builds recall, reading it again is not.
Reach the top grade on this topic
The knowledge on this topic is small and the marks are almost all in the comparison.
Never say binary search is 'better'. Say it is more efficient on a large sorted list, and then name the condition it needs. An answer that recommends binary search without checking that the data is sorted is throwing away the whole point of the question.
Quantify the difference. "Binary search is faster" is one mark at most. "Binary search halves the number of remaining items with each comparison, so a list of one million needs about twenty comparisons rather than up to one million" is the top level answer.
Handle the sorting cost honestly. Top candidates notice that if the data must be sorted first, and it is only searched once, linear search wins. That single observation is often the difference between four marks and six on an evaluate question.
- Trace a binary search on a given sorted list and count the comparisons correctly
- State the one advantage of linear search in a single sentence
- Explain why binary search only needs one more comparison when the list doubles in size
- Decide between the two algorithms for a described scenario and justify it using the scenario's own details
Mistakes that cost marks here
- Recommending binary search on unsorted data. Binary search is only defined for a sorted list.
- Saying binary search 'splits the list in half once'. It halves the remaining list repeatedly, at every comparison.
- Claiming linear search has no advantages. It works on unsorted data and it is faster than sort plus binary search for a one off lookup.
- Comparing algorithms on tiny lists and concluding one is better. Efficiency questions are about behaviour as the list grows.
- Counting the comparisons wrongly in a trace by forgetting that the middle item is itself compared before the list is halved.
Binary search on a list of one billion items needs at most 30 comparisons. Linear search on the same list needs up to one billion. That is the difference between a task finishing before you have looked up from the keyboard and a task you would abandon.
Knowledge check
Exam-style questions
Five written questions in the style of the real paper. Write a full answer, then let the marker check it against the mark scheme.
- LThe middle item of the list is examined
- LIf it matches the target the search stops
- LIf the target is smaller the upper half is discarded, and if larger the lower half is discarded
- LThe process repeats on the remaining half until the item is found or no items remain
A binary search first examines the item in the middle of the sorted list. If that item is the one being searched for, the search stops and reports success. If the target is smaller than the middle item then every item to the right of the middle can be discarded, and if it is larger then every item to the left can be discarded, because the list is in order. The search then repeats on whichever half remains, examining its middle item, and continues halving until the target is found or until no items are left, at which point the value is known not to be in the list.
- LLinear search requires up to 1024 comparisons
- LBinary search requires up to 10 or 11 comparisons
A linear search must compare every item in the worst case, so it requires up to 1024 comparisons. A binary search halves the remaining list at each step, and 1024 can be halved ten times to reach a single item, so it requires at most about ten or eleven comparisons.
- LA linear search does not require the data to be sorted
- LSo it can be used on data that arrives in a random order, or where sorting would cost more time than it saves
The advantage of a linear search is that it does not require the list to be in any particular order, whereas a binary search only works on sorted data. This means a linear search can be used immediately on data that arrives in a random order, and for a list that is searched only once it is often faster overall, because sorting the list first would take considerably more time than the linear search itself.
- LBinary search should be used
- LThe data is already sorted, which is the condition binary search requires
- LBinary search halves the number of remaining records with each comparison
- LSo it needs about 23 comparisons rather than up to 5 million
- LThe saving is repeated on every one of thousands of lookups per hour
The company should use a binary search. The records are already sorted by customer number, so the one condition that binary search requires is satisfied and no sorting cost has to be paid. Binary search compares the target with the middle record and then discards half of the remaining records, repeating until the record is found, so the number of comparisons grows extremely slowly as the data grows. On five million records it needs roughly twenty three comparisons in the worst case, whereas a linear search would need up to five million. Because the system performs thousands of lookups every hour, that saving is multiplied thousands of times over, so the difference between the two algorithms is the difference between an instant response and a system that cannot keep up.
- LRun time depends on the hardware the program is tested on
- LEfficiency counts the number of steps or comparisons, which is independent of the machine
- LSo efficiency predicts how the algorithm will behave as the amount of data grows
The time a program takes to run depends on the computer it is tested on, so a poor algorithm on a fast processor can appear quicker than a good algorithm on a slow one, which tells you nothing about the algorithms themselves. Measuring efficiency instead counts the number of steps or comparisons the algorithm performs, and that count is a property of the algorithm rather than of the hardware. It also shows how the work grows as the data set grows, which is what actually matters, because two algorithms that look identical on a hundred items can differ by a factor of thousands on a million.