Linear Search
Checks each element in order until the target appears.
- Comparisons 0
- Result still searching
- compare
- found
- excluded
Pseudocode
1 for i from 0 to n - 1
2 if a[i] == target
3 return i
4 return -1
Step log
How it works, runtime and memory
Linear search is the simplest search algorithm. It walks the array element by element from front to back and compares every value to the search key. As soon as the values match it returns the index. If the entire array is scanned without a match it returns -1. Because the worst case touches every element, runtime is linear (O(n)) in average and worst case; the best case has the hit on index 0 and finishes in constant time (O(1)). No extra memory is needed (O(1)). The big advantage: linear search makes no assumption about the data, in particular it does not need to be sorted, and it also works on streams or linked lists that only support sequential access.
Complexity
- Best case
O(1) - Average case
O(n) - Worst case
O(n) - Extra space
O(1)
When to use it
Works on unsorted data and is the only option when the data lives in a plain list or a stream that only allows sequential access. For larger sorted data sets with random access binary search is orders of magnitude faster.