A simple method for finding an element within a list. It sequentially checks each element of the list until a match is found or the whole list has been searched. It is one of the simplest searching algorithms.
1 2 3 4 5 6 7 8
{
"arr": "[2, 8, 5, 12, 16, 23, 38, 56, 72, 91]",
"target": 16
}Overview
Linear Search checks the elements one by one, from the first to the last, until it finds the target or runs out of elements. It makes no assumptions about the data: the array can be unsorted, contain duplicates, or hold values of any type that supports equality.
Because it may have to look at every element, its running time grows in direct proportion to the size of the array. That sounds slow, but for small arrays it is often the fastest option in practice, since it has no setup cost and walks memory sequentially, which CPUs handle very well.
In the default example the array holds ten values and the target is 16. The search compares 2, 8, 5 and 12 before finding 16 at index 4, so it returns 4 after five comparisons.
Step by step
- Start at index
i = 0. - If
arr[i]equals the target, returni. - Otherwise increment
i. - If
ireaches the end of the array, return-1to signal 'not found'.
Complexity
| Case | Cost | Why |
|---|---|---|
| Best case | O(1) | The target is the first element. |
| Average case | O(n) | On average about half the array is scanned. |
| Worst case | O(n) | The target is last or missing. |
| Extra space | O(1) | Only the loop index. |
When to use it
- Unsorted data, where sorting first would cost more than the search itself.
- Small arrays (tens of elements) and one-off lookups.
- Linked lists and streams, where you cannot jump to the middle anyway.
Common mistakes
- Repeated linear searches over the same large array add up quickly — build a hash set or sort once instead.
- Returning inside the loop on the first mismatch is a classic bug that only checks the first element.
- Comparing objects with
===checks identity, not equal contents.
A dry run is the best way to check your understanding of Linear Search: follow each row, predict the next one, and compare. The run below takes 12 steps in total. Steps that only re-print loop counters are left out so the decisions stand out. The Line column refers to the line numbers in the code listing above.
- Input
- 2,8,5,12,16,23,38,56,72,91
- Target
- 16
- Result
- return value = 4
| Step | Line | Array | What happens |
|---|---|---|---|
| 1 | 1 | [2, 8, 5, 12, 16, 23, 38, 56, 72, 91] | target = 16 |
| 3 | 3 | [2, 8, 5, 12, 16, 23, 38, 56, 72, 91] | i = 0, arr[i] = 2, target = 16, condition = 2 === 16 |
| 5 | 3 | [2, 8, 5, 12, 16, 23, 38, 56, 72, 91] | i = 1, arr[i] = 8, target = 16, condition = 8 === 16 |
| 7 | 3 | [2, 8, 5, 12, 16, 23, 38, 56, 72, 91] | i = 2, arr[i] = 5, target = 16, condition = 5 === 16 |
| 9 | 3 | [2, 8, 5, 12, 16, 23, 38, 56, 72, 91] | i = 3, arr[i] = 12, target = 16, condition = 12 === 16 |
| 11 | 3 | [2, 8, 5, 12, 16, 23, 38, 56, 72, 91] | i = 4, arr[i] = 16, target = 16, condition = 16 === 16 |
| 12 | 4 | [2, 8, 5, 12, 16, 23, 38, 56, 72, 91] | return value = 4 |