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.
- 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.
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 |
- 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.
Loading the question
This question is in Brainlag Plus