---
title: "Linear search"
url: https://algopath.pro/patterns/linear-search
language: en
summary: "Walk the collection from one end and stop at the first item that matches. No order, no structure and no setup are needed."
updated: 2026-08-24
---

# Linear search

Walk the collection from one end and stop at the first item that matches. No order, no structure and no setup are needed.

## How does Linear search work?

Start at the first element of the collection. Ask whether it is the one you want.

If it matches, stop and return its index. There is no reason to look further.

If it does not, move to the next element. Ask the same question again.

When the end arrives with no match, report failure. Minus one or null is the usual answer.

Nothing at all is assumed about the data. It may be sorted, shuffled or still arriving.

The worst case reads every element once. The best case reads exactly one.

- `i = 0, value 5` Looking for 2 in [5, 8, 2, 9]. The first element misses.
- `i = 1, value 8` Still no match. Move on to the next index.
- `i = 2, value 2` This element equals the target.
- `return 2` The index goes back at once. The 9 is never read.
- `target 7 gives -1` A missing value costs a whole pass. That is the worst case.

## When should you use Linear search?

- unsorted array
- check every element
- no order guarantee
- find first/any match
- small n or one-time scan

## What is Linear search confused with?

- **Binary search (array)** - Binary search needs sorted data and pays log n. A scan reads anything, in any order.
- **Hash set / map** - A map answers instantly but has to be built first. For a single lookup the scan is cheaper.
- **Two pointers (same direction)** - That pair rewrites the array while it scans. A search only ever reads.
- **Sliding window (variable)** - A window carries a description of a live span. A scan carries at most the best seen so far.
- **Elementary sorts (selection, bubble, insertion)** - Sorting first costs O(n log n) and pays off across many searches. One lookup does not repay it.

## What is the time and space complexity of Linear search?

n up to roughly 1e7 gives O(n) time and O(1) space. Bigger, or repeated, wants a real structure.

## A worked example of Linear search

### First character that never repeats

You get a string. Return the index of the first character that appears exactly once.

If every character repeats, return minus one.

Count every character in one pass. A map keyed by the character is enough.

Then scan the string again from the left. Return the first index whose count is one.

```javascript
function firstUniqChar(s) {
    const count = new Map();

    for (const c of s) {
        count.set(c, (count.get(c) ?? 0) + 1);
    }

    // the second pass is a plain scan: the first hit wins
    for (let i = 0; i < s.length; i++) {
        if (count.get(s[i]) === 1) return i;
    }

    return -1;
}
```

## Common mistakes with Linear search

- **Scanning inside another loop** A scan per element turns O(n) into O(n squared). Build a map once instead.
- **Returning the value instead of the index** Most of these tasks want the position. A value cannot say where it was found.
- **Forgetting the not-found case** A loop that ends with no match still has to return something. Pick minus one and stay with it.
- **Scanning data that was already sorted** Sorted input makes binary search far cheaper. Check the input before writing the loop.

## Which interview problems use Linear search?

- **Linear search** The plain form: stop at the first match.
- **First unique character in a string** Count once, then scan for a count of one.
- **Find the maximum** Keep the best seen and compare each element against it.
- **Contains duplicate on tiny input** A nested scan is fine when n is very small.
- **Missing number** Scan and compare each index against the value expected there.
- **Find all indices of a value** The same scan, but it does not stop at the first hit.
- **Majority element** One pass with a counter gives the Boyer-Moore vote.

## JavaScript

```javascript
function linearSearch(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) return i;
    }
    return -1;
}
```

## Python

```python
def linear_search(arr, target):
    for i, x in enumerate(arr):
        if x == target:
            return i
    return -1
```

## PHP

```php
function linearSearch(array $arr, $target) {
    foreach ($arr as $i => $x) {
        if ($x === $target) return $i;
    }
    return -1;
}
```