DSA Searching
Linear Search
You need the first warehouse slot whose barcode equals the scan. The list is unsorted, arrives as a stream, and the match is often near the front. Sorting for binary search would cost more than the scan itself.
Linear search examines candidates in order until its is satisfied or the input ends. It needs no ordering, no preprocessing, and not even random access: the same idea works on arrays, lists, generators, and files.
What happens first?
First, last, any, or all matches? How is not-found reported?
State what is already ruled out before each check.
Stop only when the contract allows it.
Beat or lose to binary/hash?
Tiny n, unsorted data, or early hits favor a scan.
What actually happens
Naive idea: “just loop until you find it.” That works, but an incomplete contract produces wrong answers: returning early for “last match,” treating 0 as not-found, or calling the scan inside an n-iteration loop and creating Θ(n²) work.
Better idea: write the invariant. For first occurrence, before index i no earlier cell holds the target. Equality at i is then the first hit; i = n proves absence. is part of correctness when the contract asks for one match.
The scan still fails on unbounded streams without a limit, when equality semantics disagree (case, NaN, identity), or when the structure mutates under the cursor. Without order or an index, an adversary can force Θ(n) inspections: that worst case is optimal, not a bug.
Invariant
For first-occurrence search: before checking index i, no index in [0, i) contains the target. Every miss extends the prefix; a hit is therefore the leftmost one.
How to choose linear search
1. Tiny n or cold data? A tight forward scan has predictable memory access and almost no setup. Binary search jumps and branches; on small arrays the constants often win for the scan.
2. Unsorted, one-off, or streaming? Sorting first is Θ(n log n), which loses to a single Θ(n) pass. Streams and linked lists have no cheap midpoint. Prefer linear (or a hash index if many exact queries share the data).
3. Early exit likely? If the hit is often near the front, expected comparisons are far below n. Binary search still pays about log₂ n even on a hit at index 0.
Quantitative check
n = 32, target at index 3: linear does 4 comparisons and returns. Binary search still needs about 5 probes on a sorted copy, plus the cost of sorting if the data was unsorted. At n = 10⁷ with a unique target equally likely anywhere, expected successful scans need about 5 × 10⁶ comparisons: then binary or hashing wins if order or an index already exists.
The loop invariant in detail
For first-occurrence search, before iteration i:
- Initialization: at
i = 0, the processed prefix is empty. - Maintenance: if
a[i]differs, extending the checked prefix preserves the claim. - Match: if
a[i]equals the target, the invariant proves no earlier match exists. - Termination: if
i = n, the checked prefix is the whole input, so the target is absent.
The order is policy
Left-to-right gives the smallest matching index. Right-to-left gives the largest. In an unordered collection, “first” means first in traversal order, not smallest value.
Early exit is correctness
Returning early is valid only when the contract asks for one or the first match. It is wrong for “all matches,” frequency, or the last occurrence.
One pass is optimal without structure
For an unsorted input and equality-only access, an adversary can put the sole target in the last unchecked position. Any correct worst-case algorithm must inspect all n values.
Interactive search-contract lab
Compare first-match early exit, all-occurrences collection, and a classical sentinel miss. Each mode exposes the invariant that makes its result trustworthy.
Search-contract laboratory
The traversal is simple; the return contract determines when the algorithm may stop and what evidence it must preserve.
target 4 · stop at first
Step 1 / 2
Comparisons so far
1
Matches recorded
∅
Outcome
continue
Current action
Compare a[0] = 8 with 4. They differ, so advance.
Loop invariant
Before checking index 0, the empty prefix contains no match.
Original visualizer · preserved
Interactive linear search demo
Watch the scan inspect cells from left to right and stop as soon as the target is found.
Canonical first-occurrence implementation
Python
def linear_search(values, target):
"""Return the first matching index, or -1."""
for index, value in enumerate(values):
if value == target:
return index
return -1TypeScript
function linearSearch<T>(values: readonly T[], target: T): number {
for (let index = 0; index < values.length; index++) {
if (Object.is(values[index], target)) return index;
}
return -1;
}Java
import java.util.List;
import java.util.Objects;
final class LinearSearch {
static <T> int firstIndex(List<T> values, T target) {
for (int index = 0; index < values.size(); index++) {
if (Objects.equals(values.get(index), target)) {
return index;
}
}
return -1;
}
}Equality is part of the API. JavaScript's Object.is treats NaN as equal to itself, unlike ===, and distinguishes 0 from -0. Pick the semantics the problem actually requires.
Variants and their output contracts
| Goal | State / stopping rule | Time | Extra space |
|---|---|---|---|
| First match | Return as soon as equality holds | Best Θ(1), worst Θ(n) | Θ(1) |
| Last match | Scan all values and overwrite the saved index | Θ(n) | Θ(1) |
| All matches | Append every matching index or value | Θ(n + k) | Θ(k) output |
| Any predicate | Stop at first value where predicate(value) is true | Θ(n × P) | Θ(1) |
| Minimum / maximum | Keep the best value and its index | Θ(n) | Θ(1) |
| Sentinel search | Place a guaranteed match after/in the data | Θ(n) | Θ(1) |
Here k is the number of returned matches and P is cost. Because k ≤ n, Θ(n + k) simplifies to Θ(n), but writing Θ(k) output and storing it are real costs. A lazy iterator can yield matches one at a time using Θ(1) auxiliary space.
Useful variant templates
All matches
Python
def all_indices(values, target):
result = []
for i, value in enumerate(values):
if value == target:
result.append(i)
return result # Θ(k) result spaceJava
import java.util.ArrayList;
import java.util.List;
import java.util.Objects;
final class AllMatches {
static <T> List<Integer> find(List<T> values, T target) {
List<Integer> result = new ArrayList<>();
for (int i = 0; i < values.size(); i++) {
if (Objects.equals(values.get(i), target)) {
result.add(i);
}
}
return result; // Θ(k) result space
}
}Predicate
Python
def find_first(values, predicate):
for i, value in enumerate(values):
if predicate(value):
return i, value
return NoneJava
import java.util.List;
import java.util.Optional;
import java.util.function.Predicate;
final class PredicateSearch {
record Match<T>(int index, T value) {}
static <T> Optional<Match<T>> findFirst(
List<T> values,
Predicate<? super T> predicate) {
for (int i = 0; i < values.size(); i++) {
T value = values.get(i);
if (predicate.test(value)) {
return Optional.of(new Match<>(i, value));
}
}
return Optional.empty();
}
}Arg max
Python
def argmax(values):
if not values:
raise ValueError("argmax of empty input")
best = 0
for i in range(1, len(values)):
if values[i] > values[best]:
best = i
return bestJava
final class ArgMax {
static int find(int[] values) {
if (values.length == 0) {
throw new IllegalArgumentException("argmax of empty input");
}
int best = 0;
for (int i = 1; i < values.length; i++) {
if (values[i] > values[best]) {
best = i;
}
}
return best;
}
}Sentinel search: one comparison in the inner loop
A classical low-level optimization temporarily puts the target in the last cell. The loop now tests equality only; it cannot run past the end because a match is guaranteed. Afterwards, restore the original value and decide whether the match was real or the .
Python
def sentinel_search(values, target):
if not values:
return -1
last = values[-1]
values[-1] = target
i = 0
while values[i] != target:
i += 1
values[-1] = last
if i < len(values) - 1 or last == target:
return i
return -1Java
final class SentinelSearch {
static int find(int[] values, int target) {
if (values.length == 0) return -1;
int lastIndex = values.length - 1;
int last = values[lastIndex];
values[lastIndex] = target;
int i = 0;
while (values[i] != target) {
i++;
}
values[lastIndex] = last;
if (i < lastIndex || last == target) return i;
return -1;
}
}How many comparisons?
Best case
1
The first inspected value matches: Θ(1).
Successful average
(n + 1) / 2
If the unique target is equally likely at each index.
Miss / worst case
n
Every value must be ruled out: Θ(n).
p and, when successful, its position is uniform, expected comparisons are p(n + 1)/2 + (1 - p)n. Real distributions are rarely uniform: putting frequently requested values earlier can reduce average latency, though reordering may violate the collection's semantics.Why linear can beat “faster” search
Small contiguous inputs
A tight forward scan has predictable memory access, little setup, and can be vectorized. Binary search makes data-dependent jumps and branches, so constants can dominate for small n.
One search on unsorted data
Sorting first costs Θ(n log n), more than the Θ(n) scan. Binary search pays off when sorted order already exists or many future queries amortize preprocessing.
Streams and linked structures
Linear search consumes one item at a time and does not require length or random access. Binary search cannot efficiently jump to a midpoint on a one-pass stream or linked list.
Expensive predicates
When each check does database, parsing, or cryptographic work, predicate cost dominates. Cache derived data, short-circuit cheap conditions first, or build an index for repeated queries.
Choosing a search strategy
| Situation | Good default | Reason |
|---|---|---|
| Small, unsorted, or one-off query | Linear search | No setup; works with any traversal. |
| Sorted random-access data, many ordered queries | Binary search | Θ(log n) query and supports boundaries/ranges. |
| Many exact-key queries, order irrelevant | Hash table | Expected Θ(1) lookup for a maintained index. |
| Values arrive incrementally | Linear scan / streaming filter | Can produce a result before the whole input exists. |
Common failure modes
Ambiguous not-found value
Document whether -1, null, or an option is returned. Never use a valid index such as 0 as the failure sentinel.
Wrong duplicate policy
Returning on equality gives the first traversal-order match, not necessarily every or the last match.
Equality mismatch
Decide case sensitivity, Unicode normalization, floating-point tolerance, object identity, and NaN behavior before coding.
Mutation during traversal
Insertion or deletion can shift indices and skip or revisit values. Snapshot, iterate safely, or prohibit concurrent mutation.
Unbounded input
A missing target means a search over an infinite stream never terminates. Add a limit, timeout, cancellation signal, or domain-specific stopping rule.
Hidden repeated scans
Calling linear search inside an n-iteration loop creates Θ(n²) work. Build a Set/Map or reorganize the computation when queries repeat.
Exercises
- For
[7, 2, 9, 2, 4]and target 2, write first-match and last-match loops. Which invariant fails if you early-exit in the last-match version? - n = 40 unsorted integers, one query. Compare total work for linear scan vs sort-then-binary-search. At what n (roughly) does sorting start to win if you will run 100 membership queries on the same array?
- Give a stream scenario where linear search with a timeout is the only correct option, and binary search is impossible. What does “not found” mean if the stream never ends?
Primary sources
- Cormen et al., Introduction to Algorithms (CLRS): sequential search and adversary arguments for unsorted search.
- Knuth, The Art of Computer Programming, Vol. 3: sequential search, sentinel technique, and average-case analysis.
- Java
List.indexOf/ Python list membership: language-level sequential search contracts.
Takeaway
Linear search is the optimal general method when the data offers no exploitable order or index. Its quality comes from a precise contract, a processed-prefix invariant, correct equality semantics, and stopping at exactly the point the requested answer is proven. It also wins on tiny n, unsorted one-offs, and early exits.