Loading...
Linear Search checks each element in order until it finds the target or reaches the end. It needs no sorting and works on any sequence, but it is O(n) — on average it inspects half the array. It is the right choice for small or unsorted data where the cost of sorting would not pay off.
Scans elements one by one until it finds the target.
a[0] = 3 ≠ 45, keep scanning.
| Best case | O(1) |
| Average case | O(n) |
| Worst case | O(n) |
| Space | O(1) |
Complexities are for the reference implementation shown; constant factors and cache behavior vary by language.
Idiomatic, copy-paste implementations. Pick your language:
Python
def linear_search(arr, target):
for i, value in enumerate(arr):
if value == target:
return i # found at index i
return -1 # not presentSearching [4, 2, 7, 1, 9, 5] step by step:
The control flow of the algorithm as a diagram: