Linear Search Visualization
Checking every element until you find what you want is the algorithm you would invent on your own, which is exactly why it is worth understanding precisely. It needs no preprocessing, no sorted input, and no assumptions — and for small or unsorted data it frequently beats the clever alternatives once you count the cost of sorting.
This isn't a canned animation. DryRun compiles and executes the code below, then draws every step from the real trace — the same values your machine would produce.
The code
int linearSearch(vector<int>& a, int target) {
for (int i = 0; i < (int)a.size(); i++) {
if (a[i] == target) return i;
}
return -1;
}
int main() {
vector<int> a = {41, 7, 93, 7, 18, 60};
cout << linearSearch(a, 7) << endl;
cout << linearSearch(a, 93) << endl;
cout << linearSearch(a, 5) << endl;
return 0;
}Returns the index of the first match — note that 7 appears twice and the search stops at index 1, never seeing index 3.
How it works, step by step
One pass, one comparison per element
The index i walks from 0 upward and each element is tested exactly once. There is no state to maintain beyond i, which is why the function is trivially correct and almost impossible to get subtly wrong.
Returning early is the whole optimisation
return i inside the loop means the function stops the moment it succeeds. On average a present target is found halfway through, so the expected work is n/2 comparisons even though the worst case is n.
Absence costs full price
A missing target forces the loop to run to completion. If most of your lookups are misses, linear search performs at its worst case every single time — that asymmetry is what usually justifies switching to a hash set or a sorted array.
First match, not best match
The function returns the earliest index that matches. If you need the last occurrence, the count, or all positions, the loop body has to change; swapping in a different search algorithm will not fix it.
Why it survives
It works on unsorted data, on linked structures, on streams you can only read once, and on comparisons that are not orderings (matching by predicate rather than by <). None of the faster searches do all of that.
Complexity
Every element may need one comparison, so time scales linearly; it stays O(n) no matter how the data is arranged, which makes it predictable but means it never improves with repeated queries the way a sorted array or hash table does.
Common bugs
Comparing a signed i against an unsigned size()
for (int i = 0; i < a.size(); i++) makes the compiler promote i to unsigned. It works, but it emits a warning and turns any negative index arithmetic you add later into a wraparound to billions. Cast the size or use size_t deliberately — pick one and be consistent.
Returning 0 instead of -1 for not found
Zero is a perfectly valid index, so a caller writing if (linearSearch(...)) treats a hit at index 0 as a miss. Use -1, or return a boolean plus an out-parameter. This bug survives every test case where the target is not first.
Forgetting that the return exits the whole function
People often add a counter after the loop to tally matches and cannot work out why it is always 0 or 1. The early return leaves the function on the first hit. If you want to count, drop the return and accumulate — stepping through shows execution leaving the function on iteration 1.
Reaching for binary search too early
If you sort an unsorted array just to run one binary search, you have paid O(n log n) to save O(n). Sorting only pays off when you will search the same array many times. Measure the number of queries before you optimise the search.
Each of these is easier to see than to describe — step through it and watch the values change. Run it in DryRun.
Frequently asked
When is linear search better than binary search?
When the data is unsorted and you will only search it once or twice, because sorting first costs more than the scan you avoided. It is also better for very small arrays — under roughly 20 to 50 elements the simple loop wins on real hardware thanks to cache locality and branch prediction, regardless of the asymptotics.
What is the time complexity of linear search?
O(n) in the worst and average case, O(1) in the best case when the target is the first element. A failed search always costs the full n comparisons because the loop cannot conclude the item is absent until it has checked everything.
Does linear search work on unsorted data?
Yes, and that is its main advantage. It makes no assumption about order because it tests every element individually rather than inferring anything from position. That also means it works with equality-only comparisons where no ordering exists.
How do I find all occurrences instead of the first?
Remove the early return and push each matching index into a result vector, returning it after the loop. The scan then always costs a full O(n) pass since it cannot stop early, and the caller gets every position rather than just the earliest.