Searching & Symbol Tables

Searching is not one algorithm. “Find this key” might mean return any equal item, the first duplicate, an insertion boundary, the value associated with a unique key, the predecessor, every key in an interval, or every string with a prefix. The query contract determines what information the representation must preserve; only then does linear search, binary search, hashing, or a tree become a sensible choice.

A symbol table is the reusable abstraction behind key-based search. It maps keys to values while hiding whether the current representation is a sorted array, a balanced tree, or a hash table.

Specify the query before choosing the structure #

Common contracts differ in ways that affect both semantics and asymptotic cost:

The same application may need several of these. A compiler's symbol table might need exact lookup by identifier inside a scope; a time-series index needs lower bounds and ranges; an autocomplete index needs prefixes. “Dictionary” and “map” usually mean unique-key exact lookup, while an ordered dictionary additionally promises order-sensitive operations.

Do not hide these decisions in an implementation accident:

• Unique map: inserting an existing key replaces its value.
• Multimap: one key may have several values, so lookup returns a range or collection.
• Set: store keys without separate values; membership is the central operation.
• Index: values are record locations, and additional consistency obligations connect index entries to a primary store.

An absent key must be distinguishable from a present key whose value happens to be null, zero, or empty. Prefer an explicit option/result or a separate membership operation over a sentinel that can also be valid data.

Linear search is the honest baseline #

For an unsorted sequence, scan from one end until the target is found or the sequence ends:

for i in 0 .. length(a)-1:
    if equivalent(a[i], target):
        return i
return not_found

Worst-case work is $n$ comparisons, expected work for a uniformly positioned successful target is roughly $(n+1)/2$, and a miss examines all $n$ elements. That sounds inferior until the constants and update costs are included:

• no preprocessing or auxiliary index;
• sequential memory access, which makes good use of cache lines and prefetching;
• constant-time append to a dynamic array;
• immediate support for predicates that do not define a useful ordering;
• excellent behavior when $n$ is small or only one search will ever occur.

Building an index costs time and memory. If a collection of $n$ items will be searched only once, sorting it for $O(n\log n)$ work merely to save one $O(n)$ scan is normally a loss. Repeated queries can amortize that preparation.

Binary search finds a boundary #

The most robust formulation does not search directly for equality. It finds the first position where a monotone predicate changes value. For lower_bound(x) on an ascending random-access sequence, the desired boundary is

$$i=\min\{j\mid \neg(a[j]<x)\},$$

with $i=n$ when every element is less than $x$.

Use a half-open interval [lo, hi):

def lower_bound(a, x):
    lo = 0
    hi = len(a)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if a[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo

The decisive loop invariants are:

1. every index below lo has an element strictly less than x;
2. every index at or above hi has an element not less than x;
3. the boundary remains in the closed index interval [lo, hi];
4. each iteration strictly decreases hi - lo.

If a[mid] < x, the boundary must be after mid, so discard [lo, mid]. Otherwise mid may itself be the answer, so keep it by setting hi = mid. When the interval is empty, lo == hi is the only possible boundary.

The midpoint form lo + (hi - lo) // 2 avoids overflow in fixed-width integer arithmetic that can affect (lo + hi) // 2.

Worked trace with duplicates #

Find lower_bound(5) in

index:  0  1  2  3  4   5   6
value:  2  5  5  5  9  12  18

The first 5 is at index 1. upper_bound(5) uses the symmetric partition “elements less than or equal to 5 / elements greater than 5” and returns 4. Thus the equal-key range is [1,4), and its multiplicity is 4 - 1 = 3.

Exact lookup is a boundary plus a check:

i = lower_bound(a, x)
found = i != length(a) and equivalent(a[i], x)

For an ordering comparator less, equivalence is often

$$\neg less(a,b)\land\neg less(b,a),$$

not necessarily an independent ==. Python's bisect deliberately uses only less-than comparisons. Rust's slice search may return any matching duplicate unless the caller uses partition boundaries to select the first or last one.

The true binary-search cost model #

Each iteration halves the candidate interval, so a random-access range needs at most about $\log_2 n$ comparisons. But “$O(\log n)$ binary search” can hide three different costs:

1. Comparisons: logarithmic under the partition precondition.
2. Movement to the midpoint: constant for arrays and random-access iterators; potentially linear in total for linked or forward-only ranges. The C++ working draft explicitly gives logarithmic comparisons but a linear number of iterator steps for non-random-access iterators.
3. Memory latency and comparison cost: probes jump across the array and may touch a different cache line each time; comparing long strings or recomputing an expensive key projection can dominate index arithmetic.

For a sorted dynamic array, finding an insertion position is $O(\log n)$, but opening a slot shifts $O(n)$ elements. Python's official insort documentation calls this out directly: linear insertion dominates logarithmic search.

This produces a common and useful workload split:

• build or update rarely, query and scan ranges often → sorted contiguous array;
• update continually while preserving order → balanced tree;
• exact key lookup without ordered queries → hash table.

Symbol-table representations #

Assume $n$ stored associations, random-access contiguous arrays, a properly balanced comparison tree, and a hash table kept within its load policy. These are model costs, not universal implementation promises.

k is the number of reported range results, and $L$ is the number of inspected key units (bytes, code units, digits, or another declared alphabet). $B$ is effective branching factor in the external-memory model. See External-Memory Algorithms for why block transfers, not CPU comparisons, dominate that last row.

The table also explains why “a symbol table is a hash table” is false. Hashing is one implementation of the exact-lookup contract. Once clients ask for min, predecessor, rank, or [a,b) iteration, equality alone is insufficient and an order-preserving representation becomes necessary.

Equality, order, and hashing must agree #

A data structure's structural invariants depend on the key relation.

For an equality-based table, equality must behave as an equivalence relation. For a comparison-based ordered table, the comparator must induce a stable strict weak order. For a hash table, equal keys must produce equal hashes for as long as they are stored.

Violations are not cosmetic:

• mutating a key field used by ordering leaves a tree node in the wrong subtree;
• mutating a field used by hashing makes an entry unreachable in its old bucket;
• a non-transitive comparator makes “left of” and “right of” mutually inconsistent;
• case-insensitive equality combined with case-sensitive hashing permits logically duplicate keys;
• locale or collation changes can invalidate a previously sorted array or persistent index;
• floating-point NaN does not behave like ordinary total-order equality, so a container must specify the ordering/equality wrapper it uses.

Duplicates are part of the API #

“Found” is underspecified when duplicates exist. An API must promise one of:

• duplicates forbidden and an insert replaces or rejects;
• return any equivalent element;
• return the first or last equivalent element;
• return the half-open equal range [lower_bound, upper_bound);
• preserve all values for one key in a secondary collection.

Returning “any match” is enough for membership but unstable as a user-visible selection. In a sorted array, boundary search gives a deterministic range. In a hash multimap, equal values may follow bucket or insertion order, which must not be assumed unless documented.

The same care applies to absence. If a map allows null values, get(k) == null cannot distinguish missing from present-null. If insertion of a duplicate returns the previous value, a separate Boolean may still be necessary when that previous value can equal the absence sentinel.

Worked design: an event catalog #

Suppose an event service stores records with unique event_id, a timestamp, and a title. Clients require:

1. exact fetch by event_id;
2. all events in timestamp interval [start,end);
3. online insert and cancellation.

One structure cannot serve both views optimally. A robust design keeps:

• a hash map by_id: event_id → record for exact lookup;
• an ordered index by_time: (timestamp,event_id) → event_id for ranges.

The composite key makes events sharing a timestamp distinct and gives a total order. To answer the range, begin at lower_bound((start, MIN_ID)) and iterate until the key reaches (end, MIN_ID).

The new difficulty is consistency. Insert must add both entries or neither. Cancellation must remove the time key derived from the same record that by_id removes. If one write succeeds and the other fails, exact and range queries disagree. In memory this may require a lock and rollback; in a database it calls for a transaction or an index maintained by the storage engine.

Cache behavior changes the crossover point #

Asymptotics do not tell you when to leave a linear scan. An array scan reads predictable adjacent memory and can compare several compact keys per cache line. A comparison tree follows dependent pointers through separately located nodes. A hash table may touch metadata and one payload location but must first hash the key. For a dozen inexpensive keys, scanning can beat structures with better Big-O; for millions of expensive string keys, projection and cache misses can dominate comparison counts.

Measure the complete workload:

• successful versus unsuccessful lookup ratio;
• dataset size distribution, not just its maximum;
• key length and comparison/hash cost;
• update-to-read ratio;
• range result sizes;
• required iteration determinism;
• memory footprint and allocation pressure;
• hot-cache and cold-cache behavior.

Precompute comparison keys when projection is expensive and records are immutable. Python's bisect documentation specifically notes that bisection is stateless and may recompute a key function across repeated searches; a parallel array of precomputed keys can be a valid representation when updates keep the two arrays synchronized.

Mutation and concurrency #

Binary search assumes the partition remains stable throughout the operation. Concurrent insertion into the searched array can move elements, invalidate indices, and briefly destroy sortedness. Python documents its bisection helpers as not thread-safe when the same sequence is mutated concurrently.

Trees and hash tables also need a declared concurrency model. “Reads are safe” is only meaningful if no writer can rotate a tree, move entries during rehash, reclaim nodes, or mutate keys concurrently. Safe patterns include immutable snapshots, external locking, copy-on-write, or a container whose concurrent algorithm and memory-reclamation scheme are part of its contract.

Iterator and reference stability are separate from query complexity. Sorted-vector insertion relocates elements; open-addressed hash-table growth usually does too; node-based trees often keep element addresses stable while invalidating only erased nodes. Clients that retain references must choose on that axis explicitly.

Choosing concretely #

1. Tiny collection or one-off search: scan a contiguous sequence. Avoid paying for an index you will not reuse.
2. Read-mostly data with exact and range lookup: sort a compact array once; use lower_bound/upper_bound and contiguous range scans.
3. Frequent exact lookup, no ordered operations: use a hardened hash table with an appropriate key/hash policy.
4. Frequent updates plus predecessor, rank, or ranges: use a balanced search tree, augmented when rank/select is required.
5. Prefix-heavy string workload: use a trie or radix index, or lexical lower bounds if a sorted array already fits the update pattern.
6. Data larger than memory or stored by pages: use a B-tree-family index designed around the I/O block size, not an in-memory pointer tree serialized by accident.
7. Several incompatible query dimensions: maintain explicit secondary indexes and make their cross-index consistency part of the write transaction.

Failure diagnostics #

1. Is the required result membership, any match, first match, insertion point, predecessor, range, rank, or prefix?
2. Are duplicate-key and replacement semantics explicit?
3. Can absence be confused with a valid value?
4. Is the binary-searched range partitioned under the exact comparator/projection used by the search?
5. Does the midpoint calculation avoid fixed-width overflow?
6. Does the claimed logarithmic cost count iterator movement, key projection, and memory access—not only comparisons?
7. Is an $O(\log n)$ insertion-point search being misreported as an $O(\log n)$ array insertion?
8. Do equality, ordering, and hashing agree for every stored key?
9. Can a stored key mutate or can collation rules change without rebuilding the index?
10. Are secondary indexes updated atomically with the primary record?
11. Can a concurrent writer invalidate the searched range or retained references?
12. Does the chosen structure support the actual query mix rather than only the easiest benchmark?

Exercises #

1. Trace lower_bound(8) and upper_bound(8) on [1,3,3,8,8,8,10], and give the equal range.
2. Prove termination of the half-open lower_bound loop from the interval length.
3. A service builds a sorted array of one million records and performs one query. Compare its asymptotic work with a linear scan and explain which operation dominates.
4. Give a comparator that violates transitivity and show why a sorted-table search can then discard the region containing an “equal” key.
5. Design indexes for users queried by unique ID, email prefix, and creation-time range. State the invariant that every write must preserve.