Linear search

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.

Sources: Wikipedia: Linear search

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

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

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

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

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

    public static int linearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) return i;
        }
        return -1;
    }

    public static int LinearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.Length; i++) {
            if (arr[i] == target) return i;
        }
        return -1;
    }

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.

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;
}

When should you use Linear search?

Use Linear search when the problem statement says “unsorted array”, “check every element” or “no order guarantee”. A solution built on it usually runs in O(n).

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

The signal words of every pattern sit in one table, the algorithm patterns cheat sheet.

What is Linear search confused with?

Linear search is most often confused with Binary search (array), Hash set / map, Two pointers (same direction), Sliding window (variable) and Elementary sorts (selection, bubble, insertion).

• 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.

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?

Interview problems solved with Linear search include Linear search, First unique character in a string, Find the maximum, Contains duplicate on tiny input, Missing number, Find all indices of a value and Majority element.

• 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.

What is the time and space complexity of Linear search?

The target complexity of Linear search is O(n).

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