When searching is the wrong tool

title: When searching is the wrong tool
summary: Hashing, indexing and precomputation beat repeated searching every time.
difficulty: intermediate
tags: searching

Both search algorithms answer "where is this?" by looking. Sometimes the better move is to arrange things so no looking is needed.

Repeated lookups: hash first

// O(n × m): a scan per query.
const found = queries.filter((q) => items.includes(q));

// O(n + m): build once, then constant-time answers.
const pool = new Set(items);
const faster = queries.filter((q) => pool.has(q));

With 10,000 items and 10,000 queries, that is 100 million operations against 20,000. This single substitution fixes more real performance bugs than every clever algorithm in this course combined.

Lookups plus order: a sorted structure

If you need "nearest key below x" or in-order iteration, hashing throws away exactly what you need. A balanced BST or a skip list gives O(log n) lookup and ordering. Databases call this an index, and it is the same idea: pay on write to make reads cheap.

Membership at scale: a Bloom filter

When the set is too large for memory and false positives are tolerable, a Bloom filter answers "definitely not present" or "probably present" in constant time and a few bits per element. Databases use them to skip files that cannot contain a key.

Prefixes: a trie

"All words starting with 'inter'" is a prefix walk, O(length of prefix), not a scan of the dictionary. Autocomplete is a trie.

The rule of thumb

The question to ask first

Before optimising a search, ask how often it runs. Optimising a once-per-request scan over 50 items is wasted effort; the same scan inside a loop over 50,000 users is the whole problem. Complexity analysis tells you what to fix, and profiling tells you where — you need both.