Linear Search
Checks each value from left to right until it finds the target or reaches the end of the array.
How it works
Linear search checks the values one by one, from the first to the last. At each index it compares the value with the target. If they are equal, it returns that index right away. If it reaches the end without a match, the target is not in the array and it returns -1.
Each check only rules out the one value it looked at, because the array can be in any order: a value being too small or too large says nothing about its neighbours. That's why, in the worst case, it has to look at every value.
When to use it
Linear search is the right choice for small arrays, for arrays that aren't sorted, and for searching once: sorting first so you can binary search costs more than a single linear pass. It also works on anything you can only walk through in order, like a linked list or a stream.
Complexity
| Case | Time | When |
|---|---|---|
| Best | O(1) | The target is the first value |
| Average | O(n) | The target is somewhere in the middle |
| Worst | O(n) | The target is the last value, or isn't there at all |
| Extra space | Why |
|---|---|
| O(1) | It only keeps the current index |
Implementations
function linearSearch(array, target) {
for (let i = 0; i < array.length; i++) {
if (array[i] === target) {
return i;
}
}
return -1;
}
def linear_search(array, target):
for i, value in enumerate(array):
if value == target:
return i
return -1
#include <vector>
int linearSearch(const std::vector<int>& a, int target) {
const int n = static_cast<int>(a.size());
for (int i = 0; i < n; i++) {
if (a[i] == target) {
return i;
}
}
return -1;
}