Lesson 2 · Core algorithms

Searching Algorithms

Every search algorithm buys speed with a precondition. Linear search assumes nothing and pays O(n). Binary search demands sorted data. Hashing demands extra memory. Trees demand maintained order. The data decides which one is even available.

What Each Method Demands of the Data

Searching means locating an element, or establishing that it is absent. Every method trades what it requires of the data against what it costs per query, and choosing well is a matter of matching those two against the actual workload.

Linear search requires nothing at all. Scan from one end until the target is found or the data runs out — O(n), no preprocessing, works on any collection in any order, including a linked list or a stream that cannot be revisited.

Binary search requires the data to be sorted and randomly accessible. Given both, it halves the candidate range with each comparison, at O(log n). Neither requirement is free: sorting costs O(n log n) up front, and random access rules out linked lists.

Hash lookup requires a hash function and spare memory. It computes the location rather than searching for it, at O(1) average, and requires no ordering of any kind. What it gives up is ordering entirely — the price is paid in what it cannot answer.

Tree search requires an ordering relation and a balanced structure. It descends comparing at each node, at O(log n), and keeps the data sorted throughout, so it answers questions hashing cannot.

The decision is therefore less about which is fastest and more about how many queries there will be. One search over unsorted data should be linear — sorting first costs more than the scan it saves. Thousands of searches justify the preprocessing several times over. This crossover is the single most useful thing to reason about explicitly.

Linear needs nothing; binary needs sorted, random-access data
Hashing needs memory and a hash function, and discards ordering
Trees need an ordering and maintain it
Preprocessing pays only when the queries are numerous enough

Linear and Binary Search

Linear search is worth taking seriously rather than dismissing. It is O(n), but with the smallest possible constant: a sequential scan reads memory in the order the CPU prefetches it, so it runs at close to memory bandwidth.

That makes it genuinely the fastest choice for small collections — typically under roughly 50 to 100 elements, where the branch misprediction and cache behaviour of binary search cost more than the extra comparisons. It is also the only option on unsorted data, on linked lists, and on streams.

A sentinel variant places the target at the end of the array so the loop needs only one comparison per iteration instead of two, a small but real saving on hot paths.

Binary search compares the target against the middle element and discards half the range. Twenty comparisons resolve a million elements; thirty resolve a billion. The logarithm is what makes it feel like it barely notices input size.

It is also notoriously difficult to write correctly. Two specific bugs account for most failures. The midpoint overflow — (lo + hi) / 2 can exceed the integer range when both indices are large, which was a real bug in Java's standard library for nine years. Write lo + (hi - lo) / 2 instead. And non-termination, when an update such as lo = mid fails to shrink the range because integer division rounds mid down to lo.

The reliable approach is to fix the invariant first — 'if the target exists it lies in [lo, hi)' — and derive the loop condition and the updates from it, rather than assembling them by intuition.

Two variants matter with duplicates. Lower bound returns the first element not less than the target; upper bound the first strictly greater. Together they bracket every occurrence, so the count is their difference. Standard libraries provide both — lower_bound/upper_bound in C++, bisect_left/bisect_right in Python — and using them is usually better than hand-writing the loop.

Binary search also generalises beyond arrays: given any monotone predicate over a range of candidate answers, it finds the switching point. 'Minimise the maximum load' problems are solved this way, searching the answer space rather than any stored data.

Linear search wins below ~50–100 elements on cache behaviour alone
Use lo + (hi − lo) / 2 to avoid midpoint overflow
Derive the loop from a stated invariant, not from intuition
Binary search extends to any monotone predicate, not just arrays

Hash Lookup

A hash table computes where an element belongs rather than searching for it. A hash function maps the key to an integer, which is reduced modulo the table size to a bucket index, and the lookup reads that bucket directly.

The cost does not grow with the number of elements at all, giving O(1) average for lookup, insertion and deletion. For membership testing — 'have I seen this before' — nothing else comes close, and it is the reason so many nested-loop O(n²) problems collapse to a single O(n) pass.

The honest statement of complexity is O(1) average, O(n) worst case. The worst case occurs when every key lands in the same bucket, and it is not purely theoretical: because hash functions are deterministic and public, an attacker controlling the keys can craft colliding ones deliberately, turning a server's request handling quadratic. Hash-flooding attacks against major web frameworks were demonstrated in 2011, and the defence — randomising the hash seed per process — is why Python's iteration order varies between runs.

The real cost, though, is what hashing cannot do. It has no notion of order, so it cannot answer: what is the smallest key, what keys lie between two values, what is the next key after this one, or iterate in sorted order. A hash table scatters keys by design, and recovering an ordering means sorting everything at O(n log n).

That limitation is the entire reason ordered structures remain in use despite being asymptotically slower — and why std::map and std::unordered_map, or TreeMap and HashMap, both exist rather than one superseding the other.

A related structure worth naming: when memory is the binding constraint and a small error rate is tolerable, a bloom filter answers membership in roughly 10 bits per element with no false negatives — useful as a cheap pre-filter in front of an expensive lookup.

The four methods compared
Method	Preprocess	Query	Needs	Ordered queries?
Linear	None	O(n)	Nothing	No
Binary	O(n log n) sort	O(log n)	Sorted, random access	Yes
Hash	O(n) build	O(1) avg	Memory, a hash function	No
Tree	O(n log n) build	O(log n)	An ordering	Yes

O(1) average, O(n) worst — and the worst case can be induced
Unbeatable for membership testing and deduplication
No ordering: no minimum, no ranges, no sorted iteration
That limitation is why ordered structures still exist

Key reference

Terms, operations, and practical uses

Search vocabulary

TargetThe value or condition being located.
Search intervalThe region that is still capable of containing the answer.
Monotonic predicateA yes/no condition that changes direction at most once across an ordered domain.

Binary-search boundaries

Lower boundThe first position whose value is at least the target.
Upper boundThe first position whose value is greater than the target.
MidpointThe inspected position that proves which portion can be discarded.

Choose the right search

Linear searchNeeds no preprocessing and works on unsorted data.
Binary searchHalves a sorted range each step for O(log n) lookup.
Hash lookupProvides expected constant-time membership by maintaining an auxiliary index.
Binary search treeKeeps keys ordered, so range queries and successors stay cheap.
Sorting firstOrdering once pays off when a collection is searched many times.
Answer-space searchBinary-searches possible results when feasibility changes monotonically.

Implementation

Find 16 with binary search

def binary_search(values, target):
    left, right = 0, len(values) - 1
    while left <= right:
        middle = left + (right - left) // 2
        if values[middle] == target:
            return middle
        if values[middle] < target:
            left = middle + 1
        else:
            right = middle - 1
    return -1
print('index', binary_search([2, 5, 8, 12, 16, 21, 29], 16))

#include <iostream>
#include <vector>
using namespace std;
int binarySearch(const vector<int>& values, int target) {
    int left = 0, right = (int)values.size() - 1;
    while (left <= right) {
        int middle = left + (right - left) / 2; // avoids overflow
        if (values[middle] == target) return middle;
        if (values[middle] < target) left = middle + 1;
        else right = middle - 1;
    }
    return -1;
}
int main() {
    vector<int> values = {2, 5, 8, 12, 16, 21, 29};
    cout << "index " << binarySearch(values, 16) << '\n';
}

class Main {
    static int binarySearch(int[] values, int target) {
        int left = 0, right = values.length - 1;
        while (left <= right) {
            int middle = left + (right - left) / 2; // avoids overflow
            if (values[middle] == target) return middle;
            if (values[middle] < target) left = middle + 1;
            else right = middle - 1;
        }
        return -1;
    }
    public static void main(String[] args) {
        int[] values = {2, 5, 8, 12, 16, 21, 29};
        System.out.println("index " + binarySearch(values, 16));
    }
}

Watch it run

Step through it

Running on [2, 5, 8, 12, 16, 21, 29], target 16

Output

Read all 9 Steps

Sorted input, target 16 Binary search requires sorted data — that is the precondition buying the O(log n) runtime. On unsorted input, linear search at O(n) is the only correct option.
Set low = 0, high = 6 The interval [0, 6] holds every index, so the answer is somewhere inside it. This invariant — the target, if present, is always within [low, high] — must survive every iteration.
mid = 3, value 12 mid = low + (high − low) / 2 = 3. Writing it this way instead of (low + high) / 2 avoids integer overflow on large indices, a bug that sat in the JDK for nine years.
12 < 16, discard the left half Because the array is sorted, everything at or below index 3 is ≤ 12 and therefore too small. Four candidates are eliminated by a single comparison.
mid = 5, value 21 The interval is now [4, 6]. mid = 4 + (6 − 4) / 2 = 5, so inspect 21.
21 > 16, discard the right half Sorted order proves indices 5 and 6 are all too large, so high = mid − 1 = 4. Only one candidate survives.
mid = 4, value 16 low and high have converged on index 4. mid is 4 and the value there is exactly the target.
Return index 4 Three comparisons searched seven elements. The interval halves each round, so a million elements would take about twenty comparisons instead of a million.
The missing-target case Searching for 17 would run the same path, then set low = 5 with high = 4. Once low > high the interval is empty, the loop exits, and the function returns −1. That crossing is the only termination proof binary search has.

Tree Search, and Choosing

A balanced binary search tree — AVL or red-black — keeps keys ordered and searches by descending from the root, comparing at each node. Every operation is O(log n) guaranteed, and unlike a hash table the ordering survives.

That ordering is what it is for. A tree answers range queries — every key between two bounds — by descending to the lower bound and walking in order. It answers floor and ceiling queries, the nearest key not above or not below a value, which underlie interval lookups and nearest-match searches. It supports sorted iteration in O(n) with no sort. And it gives the minimum and maximum by walking left or right.

None of these is available from a hash table at any cost, so the choice between them is not about speed. If the queries are all exact-match, hash. If any query involves order, use a tree.

The tree's other advantage is a guarantee: O(log n) worst case, with no adversarial input able to degrade it. For latency-sensitive systems that predictability can outweigh hashing's better average.

B-trees are the variant for data on disk. Each node holds hundreds of keys and fills one disk block, so the tree is three or four levels deep for millions of records — and since a disk read costs about 100,000 times a memory access, minimising reads is the only thing that matters. This is why database indexes are B+ trees rather than binary trees or hash tables.

A short decision procedure covering most cases. One search on unsorted data — linear; sorting costs more than it saves. Under about a hundred elements — linear, whatever the data looks like. Repeated exact-match lookups — hash table. Any query involving order or ranges — balanced tree, or a sorted array with binary search if the data never changes. Data on disk — B+ tree. Data too large to store, membership only — bloom filter in front of the authoritative source.

The recurring theme is that the number of queries decides whether preprocessing is worth it, and the kind of query decides which structure the preprocessing should build.

Trees answer range, floor, ceiling and sorted-iteration queries
Hashing is faster on average; trees guarantee O(log n)
B+ trees minimise disk reads, which is why databases use them
Query count decides whether to preprocess; query kind decides into what