# Linear Search, Explained Step by Step

> Check every value, left to right, until you find the key.

Searching algorithm. Interactive version, with a step-by-step visualizer of a real recorded run: https://www.tmread.me/algorithms/linear-search

## Complexity

| | Big-O | Why |
|---|---|---|
| Best time | O(1) | The key is the first value. |
| Average time | O(n) | On average it checks about half the array. |
| Worst time | O(n) | The key is last, or missing: every value gets checked. |
| Extra space | O(1) | One index. |

## What is linear search?

Linear search looks for a value, called the key, by checking every item in order. It starts at the first item and asks “is this the key?” If yes, it returns the position. If not, it moves one step right. If it reaches the end without a match, the key isn’t there, and it returns −1.

It is the search you do when you look for a name on an unsorted paper list: top to bottom, one line at a time. It is also called sequential search.

Its big strength is that it works on any list. The values don’t have to be sorted. Every faster search on this site needs sorted input.

## How it works, step by step

Press play above. The key is shown next to the counters. The blue bar is being compared with the key, and `lo` marks where the search is. Every bar behind `lo` fades out: it has been ruled out. A green bar is the match.

1. Set `lo = 0` and `hi` to the last index.
2. Compare `a[i]` with the key.
3. If they are equal, return `i`. Done.
4. If not, everything up to `i` is ruled out, so move `lo` to `i + 1`.
5. Repeat until you find the key or pass the end. Then return −1.

Try both presets. With “present”, the search stops as soon as it hits the key. With “absent”, it has to check every single value before it can say no.

The array in this demo happens to be sorted, so the searches on this site can share the same inputs. Linear search doesn’t use that at all. It would behave the same on a shuffled list.

## Time and space complexity

Best case, O(1): the key is the first value. One comparison.

Worst case, O(n): the key is the last value, or not there at all. Every value gets checked.

Average case, O(n): if the key is equally likely to be anywhere, you check about half the list, `n/2` comparisons. Big-O drops the ½, so it is still O(n).

Space is O(1). One index, no copies.

O(n) sounds slow next to binary search’s O(log n). For a million values, that is up to a million checks versus about 20. But binary search needs sorted input, and sorting costs O(n log n). If you only search once, sorting first costs more than just looking.

## Common mistakes

- Returning −1 inside the loop, right after the first mismatch. The “not found” answer can only come after the loop ends.
- Off-by-one on the end. In Python, `range(lo, hi + 1)` includes `hi`. In a C-style loop, use `i <= hi` or `i < n`.
- Using linear search over and over on the same big list. If you search many times, sort once and use binary search, or put the values in a hash set for O(1) lookups.

## When to use it

Linear search is the right choice more often than people think:

- The list is unsorted and you only search it once or a few times.
- The list is small. For a few dozen values, a straight scan is often faster than anything clever, because it reads memory in order.
- You are searching a stream or a linked list, where you can’t jump to the middle anyway.
- You need the first match by some rule, like the first word longer than 10 letters.

Most languages have it built in: `list.index` in Python, `Array.prototype.indexOf` and `find` in JavaScript, and `slices.Index` in Go all do a linear scan.

## Code

### Python

```python
def linear_search(a, key):
    lo, hi = 0, len(a) - 1
    for i in range(lo, hi + 1):
        if a[i] == key:
            return i
        lo = i + 1
    return -1
```

### TypeScript

```ts
function linearSearch(a: number[], key: number) {
  let lo = 0, hi = a.length - 1;
  for (let i = lo; i <= hi; i++) {
    if (a[i] === key) {
      return i;
    }
    lo = i + 1;
  }
  return -1;
}
```

### Go

```go
func linearSearch(a []int, key int) int {
    lo, hi := 0, len(a)-1
    for i := lo; i <= hi; i++ {
        if a[i] == key {
            return i
        }
        lo = i + 1
    }
    return -1
}
```

## Questions

### Does linear search need a sorted list?

No. That is its main advantage. It works on any list, in any order.

### Is linear search faster than binary search?

On small lists it can be. On large sorted lists, binary search is far faster: O(log n) against O(n).

### What does linear search return if the key is missing?

By convention, −1: a position that can’t exist, so the caller knows nothing was found.

## Related algorithms

- [Binary Search](https://www.tmread.me/algorithms/binary-search.md): Check the middle of a sorted array and throw away the half that can’t hold the key.
- [Jump Search](https://www.tmread.me/algorithms/jump-search.md): Jump ahead √n at a time, then walk back through one block.
- [Exponential Search](https://www.tmread.me/algorithms/exponential-search.md): Double a bound until it passes the key, then binary search that range.

---

From The Missing README (computer science, made visible). Want to run your own code and watch every step? Join Cohort 0, the early-access group: https://www.tmread.me/#cohort