Search Algorithms

The family of search methods and when each one wins: linear scan, binary search and its boundary form, exponential search for unknown sizes, interpolation search for evenly spread keys, peak finding, and binary search on the answer.

Overview

Pick the search that fits the data

Every search answers one question: where is the thing I want, or where would it go? What you know about the data decides how fast you can answer. With no order you must look at everything. With sorted data you can throw away half of what is left at each step. With more knowledge (how the values are spread, or that they rise and then fall) you can do better still.

Linear scan — nothing — O(n) — data is unsorted, tiny, or a linked list
Binary search — sorted, random access — O(log n) — the classic sorted-array lookup or boundary
Exponential search — sorted, size unknown or target near the front — O(log k), k = target position — a stream, an unbounded list, a merge that skips ahead
Interpolation search — sorted numbers spread about evenly — about O(log log n) on average, O(n) worst — large, uniform numeric keys
Peak finding / ternary search — values rise, then fall — O(log n) — find a local maximum without sorting
Search on the answer — a yes/no test that flips once as the answer grows — O(log range × cost of test) — minimize or maximize a value under a limit

Linear scan: the baseline

A linear scan checks each element in turn and stops at the first match. It needs no order and no random access, so it is the only choice for an unsorted list or a linked list. Sorting first costs O(n log n), which is only worth it if you will search many times.

1 — O(n) — O(n log n)
k — O(k·n) — O(n log n + k log n)

Rule of thumb: one lookup, scan; many lookups, sort once (or build a hash set for exact matches).

Binary search in one table

Binary search keeps a range that must contain the answer and halves it each step. The Binary Search topic covers the templates in depth; here is the boundary form (lower bound: the first index whose value is at least the target), traced on [1, 3, 3, 5, 8, 9] for target 3.

0 — 6 — 3 — 5 — yes — keep left half: hi = 3
0 — 3 — 1 — 3 — yes — hi = 1
0 — 1 — 0 — 1 — no — lo = 1
1 — 1 — stop: answer 1

The first 3 is at index 1. Python's bisect_left returns the same insertion point, before any equal elements; bisect_right returns the point after them, so bisect_right - bisect_left counts the copies (here 3 - 1 = 2).

Python bisect_left(a, x) — first index i with a[i] >= x — the insertion point, even if x is absent
Python bisect_right(a, x) — first index i with a[i] > x — the insertion point after equal elements
Java Arrays.binarySearch(a, x) — an index of x, or -(insertion point) - 1 — with duplicates, no guarantee which copy

Exponential search: when you do not know the size

If the list has no known end (a stream, an unbounded sorted source) or the target is likely near the front, probe positions 1, 2, 4, 8 and so on until you pass the target. The target now lies between the last two probes, and a binary search inside that range finishes the job. Bentley and Yao described this approach for unbounded searching in 1976.

Here is the trace on 16 sorted values, looking for 26 (it sits at index 10).

1 — 4 — yes — double to 2
2 — 5 — yes — double to 4
4 — 9 — yes — double to 8
8 — 21 — yes — double to 16
16 — past the end — binary search indices 8 to 15

Doubling takes about log k steps to pass position k, and the binary search inside a range of size about k takes another log k. The total is O(log k), which beats O(log n) when the target sits near the front. CPython's list sort uses the same idea, which its notes call galloping, to skip over long runs while merging.

Interpolation search: guess where the value should be

Binary search always probes the middle. Interpolation search probes where the target should be if the values rise evenly, the way you open a phone book near the back for a name starting with W.

pos = lo + (target - a[lo]) * (hi - lo) // (a[hi] - a[lo])

[10, 20, ..., 100] (even steps) — 70 — 1 — the first guess, index 6, is exact
[1, 2, ..., 9, 1000] (one huge value) — 9 — 9 — the huge last value drags every guess to the left end

On keys spread evenly, the average number of probes is about log log n (Perl, Itai and Avni, 1978). For a billion keys that is about 5 probes, against about 30 for binary search. On skewed keys it falls to O(n), so it is a tool for big uniform numeric data, not a default.

Peak finding: search without sorting

A peak is an element larger than its neighbors, with the ends treated as minus infinity. The array is not sorted, but one comparison still tells you which half must hold a peak: if a[mid] < a[mid + 1], the values rise to the right, and a peak lies on the right. Otherwise mid itself or something to its left is a peak.

0 — 6 — 3 — 3 — 5 — rising, lo = 4
4 — 6 — 5 — 6 — 4 — falling, hi = 5
4 — 5 — 4 — 5 — 6 — rising, lo = 5
5 — 5 — stop: peak at index 5 (value 6)

That trace runs on [1, 2, 1, 3, 5, 6, 4]. Index 1 is also a peak; the method returns one peak, not all of them. Ternary search uses the same idea on a function that rises and then falls: compare two inner points and drop the third that cannot hold the maximum.

Search on the answer

Some problems ask for the smallest (or largest) value that satisfies a limit, such as the slowest eating speed that still finishes in time. You cannot sort the answers, but you can test one: given a speed, can Koko finish? If a speed works, every faster speed also works. The yes/no test flips exactly once, so binary search finds the flip.

Koko has piles [3, 6, 7, 11] and 8 hours. At speed k, a pile of p bananas takes ceil(p / k) hours.

1 — 27 — no
2 — 15 — no
3 — 10 — no
4 — 8 — yes
5 — 8 — yes
11 — 4 — yes

The search checks speeds 6, 3, 5 and 4 and returns 4. The cost is O(n log m): log m tests over the range of speeds (m is the largest pile), each test reading all n piles.

What you will be able to do

Choose between linear, binary, exponential and interpolation search from what the data guarantees.
Trace a lower-bound search and explain what bisect_left and bisect_right return.
Explain why exponential search costs O(log k) and when interpolation search breaks down.
Find a peak in O(log n) on data that is not sorted.
Spot a search-on-the-answer problem and write its monotonic test.

When to use it

Looking up a value or its insertion point in sorted data
Finding the first or last occurrence of a value
Searching a sorted source whose size you do not know
Searching a rotated sorted array
Finding a local maximum or minimum without sorting
Minimizing or maximizing a value under a limit (speed, capacity, largest sum)
Computing an integer square root or similar value by bisection

More Coding & DSA topics

Start free on Cariara · Coding problems · System design studio