SearchingAlgorithmaka sequential search, brute-force search

Linear Search

Scan elements one by one until the target is found or the input is exhausted.

▶ VisualizePattern: Two PointersPractice (3)
Progress

Overview

Linear search examines each element in order and stops at the first match. It makes no assumptions about the data: unsorted, sorted, duplicates, linked lists, streams — anything that can be iterated can be linearly searched.

It is the baseline every other search is measured against. O(n) sounds slow, but for small n (roughly under 32–64 elements) a tight linear scan often beats Binary Search in wall-clock time because it is branch-predictable and cache-friendly.

unsortedO(n)baselinesequential

Intuition

A mental model before the formal terms.

Looking for your keys by checking every pocket in turn. You do not need your pockets organized; you just check each one until you feel the keys. If they are not in any pocket you only know that after checking all of them.

How it works

  1. Start at index 0.
  2. Compare a[i] with target. If equal, return i.
  3. Otherwise advance i by one and repeat.
  4. If i reaches n without a match, return -1 (not found).

Why it works

Correctness is immediate: every index is visited, so if the target exists it is compared at some point and the first match is returned.

Termination: i strictly increases and is bounded by n, so the loop runs at most n times.

Recognition

How to tell a problem wants this.

  • The input is unsorted and searched only once — sorting first would cost more than the scan.
  • You need the first occurrence in original order, or you must inspect every element anyway (e.g. count matches, find min/max).
  • The container has no random access (linked list, iterator, stream), so index-halving strategies do not help.
“sorted array” → Two Pointers

Interactive visualization

Play, step, change the input. ← → and space work too.

2
0
5
1
8
2
12
3
16
4
23
5
38
6
56
7
72
8
91
9
1/7Search for 23 by checking every element from left to right. No ordering is assumed, so nothing can be skipped.
Being compared with targetTarget foundEliminated
PseudocodeLearn Linear Search →
1for i in 0 .. n-1:
2  if a[i] == target: return i
3return -1
Variables
target23
Complexity
best O(1)
avg O(n)
worst O(n)
space O(1)
Speed

Pseudocode

1for i from 0 to n - 1:
2  if a[i] == target: return i
3return -1

Implementations

1from typing import Callable, Optional, Sequence, TypeVar
2 
3T = TypeVar("T")
4 
5 
61 · The baseline: look at every element until one matches
7def linear_search(a: Sequence[T], target: T) -> int:
8    for i, value in enumerate(a):
9        if value == target:
10            return i
11    return -1
12 
13 
142 · The standard-library form, which works on any predicate
15def find_first_negative(a: Sequence[int]) -> int:
16    return next((i for i, x in enumerate(a) if x < 0), -1)
17 
18 
193 · A sentinel removes the bounds check from the inner loop
20def sentinel_search(a: list[int], target: int) -> int:
21    if not a:
22        return -1
23    last = a[-1]
24    a[-1] = target  # guarantees a match, so no i < n test is needed
25    i = 0
26    while a[i] != target:
27        i += 1
28    a[-1] = last
29    return i if i < len(a) - 1 or last == target else -1
30 
31 
324 · Unsorted data leaves no choice: every miss costs a full scan
33def contains(names: Sequence[str], name: str) -> bool:
34    return name in names
Walkthrough
  1. enumerate(a) yields index/value pairs, which is the Pythonic replacement for range(len(a)) plus indexing.
  2. next((i for i, x in enumerate(a) if x < 0), -1) is the one-expression "first index matching a predicate" — the generator is lazy, so it stops at the first hit.
  3. sentinel_search mutates the list and restores it; the final conditional distinguishes a genuine hit from stopping on the planted sentinel.
  4. name in names dispatches to __contains__, which for a list is a linear scan and for a set or dict is a hash lookup — same syntax, wildly different cost.
  5. == in Python is structural for built-in types, so linear_search finds an equal tuple or list, unlike the === versions in JS/TS.
Complexity (this implementation)
time O(n) worst and average, O(1) best · space O(1)

in and list.index run their loop in C and are several times faster than an equivalent Python-level for, at the same O(n).

Language notes
  • list.index(x) returns the index but raises ValueError on a miss instead of returning -1 — wrap it in try/except or use the next(..., -1) idiom.
  • in on a set or dict is O(1) average; on a list or tuple it is O(n). Swapping the container is the entire optimisation.
  • == compares by value for built-ins and by __eq__ for custom classes; is compares identity and is only correct for singletons like None.
  • bisect.bisect_left is the sorted-input answer, and operator.countOf(a, x) counts occurrences in C.
Common mistakes in this language
  • Using list.index without catching ValueError, which turns a normal miss into an exception at runtime.
  • Writing if name is target for strings — it works for short interned literals and fails for computed strings, which is the worst kind of bug.
  • Calling x in big_list inside a loop instead of building a set once, which is the classic accidental O(n²).
Language differences that matter here
  • Miss convention: C++ returns end(), Python list.index raises ValueError, and JS/TS return -1 — three different contracts for the same event.
  • Equality: Python == is structural (a list equals an equal list), JS/TS === is reference identity for objects, and C++ operator== is whatever the type defines.
  • The idiomatic call differs: std::find_if with a lambda, Array.prototype.findIndex, and next((i for ...), -1) — all three express "first index matching a predicate" in one line.
  • Sparse arrays exist only in JS/TS, where indexOf skips holes; C++ vectors and Python lists have no holes to skip.

Complexity

Best
O(1)
Average
O(n)
Worst
O(n)
Space
O(1)

Average is n/2 comparisons for a present target, n for an absent one.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Unsorted data queried once or a handful of times.
  • Very small arrays (tens of elements) where constant factors dominate.
  • Sequential containers without random access: linked lists, iterators, file streams.
  • When the match predicate is arbitrary and no ordering of the data corresponds to it.
Avoid it when
  • Sorted data with repeated queries — use Binary Search for O(log n).
  • Many membership queries on a static set — build a Hash Set for O(1) average lookups.
  • Large inputs (n ≥ 10^6) queried repeatedly; the O(n·q) total is too slow.

Alternatives

Binary SearchHash SetJump Search

Common mistakes

  • Returning the last match instead of the first when the problem asks for the first index.
  • Forgetting the not-found case and returning n or undefined.
  • Using linear search inside a loop over another large array, producing O(n·m) when a hash set gives O(n + m).

Interview patterns

  • Sentinel search: place the target at a[n] to drop the bounds check from the inner loop.
  • Find the first element satisfying an arbitrary predicate (find, findIndex, any).
  • Single pass to compute min/max/second-largest — the same scan structure.
  • Explain why a hash set or sorting is the improvement, then implement that.
Interview questions on this
Mock interviews

Example problems

Two SumeasyMove ZeroeseasySingle Numbereasy