Linear Search
The honest, lazy way: check every element until you find the target. No prep, no sorting needed — but slow on big lists.
Find target in unsorted list
- comparisons
- 0
- index
- —
- result
- —
- 0
def linear_search(arr, target): - 1
for i in range(len(arr)): - 2
if arr[i] == target: - 3
return i - 4
return -1
What you just watched
Linear search has one move and runs it on a loop: look at the next item; if it's the one I want, stop; otherwise keep going. The for-loop is the engine, the comparison is the decision (which we covered in Conditions). That's the whole algorithm.
On a 16-element list, the worst case is 16 comparisons — about as cheap as algorithms come. On a million-element list, the worst case is a million comparisons, and you'll feel it. That's where Binary Search comes in (sorted lists only).
Try a target that doesn't exist in the array (e.g., 999) and watch the algorithm sweep all 16 cells before giving up. That's the worst case made visible.