Linear search
easyThe only search that assumes nothing about the data - which is why it is still the right answer for a linked list, a stream, or twenty items.
O(1)Average O(n)Worst O(n)Space O(1)Saved in this browser - no sign-up, nothing sent anywhere.
How linear search works
Start at index 0, compare, move right, stop on a match. Linear search assumes nothing about the data - not sorted order, not random access, not even a known length. That is its entire value: it is the one search in this category that works on a linked list, a stream you see once, or an array in arbitrary order.
The cost tracks where the target sits. A successful search inspects n/2 elements on average; a failed one always inspects all n. On 12 elements that gap barely matters, and below a few dozen items a plain loop is usually the fastest thing you can write - no sorting, no setup, no bookkeeping.
Every other algorithm on this page buys speed by assuming order. Binary search needs sorted input, jump search needs sorted input and forward blocks, interpolation search needs uniform values on top of that. Linear search is the baseline they are all measured against, and the fallback when their assumptions do not hold.
Step by step
- Search for 29 in [42, 17, 93, 8, 61, 29, 74, 5, 38, 55, 23, 86] - 12 elements, no order assumed.
- a[0] = 42 is not 29. Neither is a[1] = 17. Each miss simply advances i by one position.
- a[2] = 93, a[3] = 8, a[4] = 61 - three more misses. Five elements checked so far, no match yet.
- a[5] = 29 equals the target - return index 5 after exactly 6 comparisons. Nothing to the right is ever examined.
- Had the target been 30, the loop would have fallen off the end and returned -1 after all 12 comparisons - a failed search always costs the full length.
Complexity
| Best case time | O(1) |
|---|---|
| Average time | O(n) |
| Worst case time | O(n) |
| Space | O(1) |
Reference implementation
Python
def linear_search(a, target):
for i, x in enumerate(a):
if x == target:
return i
return -1JavaScript
function linearSearch(a, target) {
for (let i = 0; i < a.length; i++) {
if (a[i] === target) return i;
}
return -1;
}Java
static int linearSearch(int[] a, int target) {
for (int i = 0; i < a.length; i++)
if (a[i] == target) return i;
return -1;
}Worth noticing
The only search that works on unsorted data
Every faster search here buys its speed by assuming order. Linear search assumes nothing, which is why it is still the right answer for a linked list, a stream, or an array of twenty items.
Half the array on average
A successful search inspects n/2 elements on average; a failed one always inspects all n. Set the target to something absent and watch the counter reach the full length.
Common pitfalls
- Returning the loop counter after the loop ends instead of -1 - the caller cannot tell 'found at the last index' from 'not found at all'.
- Scanning on after the first hit. If any match will do, return immediately; the early exit is what makes the average successful case n/2 instead of n.
- Using it inside a hot loop - m lookups against the same array cost O(n × m). Sort once for binary search, or build a hash map, when lookups repeat.
- In JavaScript, comparing objects with === checks identity, not contents - a linear search for an equal-looking object misses unless you search with a predicate instead.
Where it is used
- What indexOf, includes, C++ std::find, and Python's in operator on a list actually run underneath.
- Linked lists and streams - structures with no random access, where the faster searches cannot even take their first step.
- Small arrays: below a few dozen elements, the simple loop is the pragmatic choice.
- The interview baseline - state it first, then justify the sorted-input assumption that unlocks binary search.
Frequently asked questions
What is the time and space complexity of linear search?
Best case O(1) when the target sits at index 0, average and worst case O(n) - a successful search inspects about n/2 elements, a failed one all n. Space is O(1): one index variable and nothing else.
When is linear search better than binary search?
When the data is unsorted and searched once - sorting first costs O(n log n), far more than one O(n) scan. Also on linked lists and streams, where binary search cannot jump to a midpoint, and on tiny arrays where the simple loop wins on plain overhead.
Does linear search work on unsorted data?
Yes - it is the only algorithm on this page that does. It compares every element against the target directly, so order is irrelevant. Every faster search here trades that freedom away: binary, jump, exponential, and interpolation search all require sorted input before they are even correct.
Which index does linear search return when the target appears more than once?
The lowest one. The scan moves left to right and returns on the first equality, so later duplicates are never reached. If you need the last occurrence instead, scan from the right, or keep overwriting a found index and return it after the loop.