Linear search and binary search
Linear search
A linear search starts at the first item and checks each one in turn until it finds what it is looking for, or runs out of items.
- It works on any list, sorted or not.
- An item's index is its position number in the list, counting from 0. If the item is at index 4 (the fifth item), the search makes 5 comparisons, because indexes start at 0.
- If the item is not there, it has to check every item before it can say so.
Step through it. Press Step, or put in your own list and the item to find.
Binary search
A binary search only works on a sorted list.
It compares the target with the middle item, then throws away the half that cannot hold it.
- Set low to the first index and high to the last index.
- mid = (low + high) DIV 2. DIV divides and drops any remainder, so the middle rounds down.
- If the item at mid is the target, stop: found.
- If it is less than the target, the target must be to the right: low = mid + 1.
- If it is more than the target, the target must be to the left: high = mid - 1.
- Repeat until found, or until low is bigger than high (the target is not there).
When a question asks which items are compared, list the item at each midpoint in order, including the last one.
A worked example: find 58 in this sorted list of 10 items, indexes 0 to 9: 3, 9, 14, 21, 30, 42, 58, 63, 77, 90.
- low = 0, high = 9, mid = (0 + 9) DIV 2 = 4. The item at index 4 is 30. 30 is less than 58, so low = 5.
- low = 5, high = 9, mid = (5 + 9) DIV 2 = 7. The item at index 7 is 63. 63 is more than 58, so high = 6.
- low = 5, high = 6, mid = (5 + 6) DIV 2 = 5. The item at index 5 is 42. 42 is less than 58, so low = 6.
- low = 6, high = 6, mid = (6 + 6) DIV 2 = 6. The item at index 6 is 58: found.
- The items compared are 30, 63, 42, 58: that is 4 comparisons.
If the target is not in the list, keep going in the same way. Every midpoint you check is one comparison. When low becomes bigger than high, stop: the search reports that the target is not there.
Binary search works on words too, as long as they are in alphabetical order. "Less than" then means "comes earlier in the alphabet": "fig" is less than "plum", so if the middle word is "fig" and the target is "plum", the target is to the right.
Which search, and why
Each comparison in a binary search halves what is left, so even huge lists need very few comparisons.
| Items in a sorted list | Linear search, worst case | Binary search, worst case |
|---|---|---|
| 8 | 8 | 4 |
| 100 | 100 | 7 |
| 1 000 | 1 000 | 10 |
| 1 000 000 | 1 000 000 | 20 |
To work out the most comparisons a binary search could need, halve the number of items again and again, dropping any remainder, until you reach 1. Count the numbers in the chain, including the first number and the 1.
For 40 items: 40, 20, 10, 5, 2, 1. That is 6 numbers, so at most 6 comparisons. A linear search of the same list could need 40, one for every item.
- Use binary search on a long list that is sorted (or that you will search many times, so sorting it once is worth it).
- Use linear search when the list is not sorted, or is short, or changes all the time. It is also simpler to write.