Linear search
Linear search checks each value in the array in order, comparing it with the target, until it finds a match or runs out of values.
When it is the right choice
Linear search is the right choice for unsorted data or a one-off search, since it needs no preparation and works on any array. It is a poor choice for repeated searches on the same large array, where sorting once and using binary search pays for itself quickly.
How it works
- Starting from the first position, compare the value at the current position with the target.
- If it matches, the target is found at this position.
- Otherwise, move to the next position and repeat.
- If every position has been checked without a match, the target is not in the array.
Worth noticing
- Its worst case and average case are both O(n) — there is no shortcut, even though this tool always runs it on a sorted copy for consistency with the other searches.
- Its best case, O(1), only happens when the target is the very first value checked.
Cost
- Best
- O(1)
- Average
- O(n)
- Worst
- O(n)
- Extra space
- O(1)