Searching Algorithms: Linear, Binary & Hash-Based Lookup

Q: When should I use binary search vs a hash table?

Use a hash table when you need fast exact lookups by key and don't care about order — it's O(1) average and the simplest fast option. Use binary search (on sorted data) when you also need ordered operations: range queries ("all values between X and Y"), finding the nearest element, or iterating in order. Binary search is O(log n) vs the hash's O(1), but it supports queries a hash can't. Match the structure to the queries you run.

Searching Algorithms

Searching — finding whether (and where) a value exists in a collection — is so fundamental it underlies databases, autocomplete, routing, and most of what software does. The dramatic differences between approaches make it a perfect lens on algorithmic thinking: a linear scan is O(n), a binary search on sorted data is O(log n), and a hash lookup is O(1). Choosing well can turn a sluggish feature into an instant one.

The key realization is that faster search usually requires structure — sorted order for binary search, a hash table for O(1) lookup, an index for a database. You invest in organizing the data so that finding things becomes cheap.

TL;DR

Linear search: O(n), works on anything, no setup.
Binary search: O(log n), but requires sorted data.
Hash lookup: O(1) average, via a hash table.
Faster search trades preprocessing/structure for query speed.

Quick Example

Binary search halves the search space each step — but only works on sorted data:

The Approaches

Linear vs Binary Search

Linear search checks each element in turn — O(n), no preconditions, fine for small or unsorted data. Binary search repeatedly halves a sorted range: compare the middle element, discard the half that can't contain the target, repeat. That halving gives O(log n) — for a million items, ~20 comparisons instead of a million.

⚠️ Binary search is only correct on sorted data. Running it on an unsorted array returns wrong results silently. If you search repeatedly, sorting once (O(n log n)) to enable O(log n) lookups pays off quickly.

Hash-Based & Indexed Search

For sheer lookup speed, a hash table gives O(1) average membership and key lookups — the reason sets and dictionaries are everywhere. The tradeoff is no ordering and worst-case O(n) under bad collisions.

At scale, databases make search fast with indexes — typically B-trees giving O(log n) lookups — so a query over millions of rows doesn't scan every one. This is the same idea (invest in structure to speed queries) applied to persistent data. See Database Indexing.

Best Practices

Use a hash set/map for frequent membership or key lookups — O(1) beats scanning.
Sort once, binary-search many when you repeatedly search a stable dataset.
Index your database columns that you filter or join on (see Database Indexing).
Match the structure to the query — range queries favor trees/sorted arrays, exact lookups favor hashes.
Don't re-sort or rebuild structures inside a loop — preprocess once.

Common Mistakes

Binary search on unsorted data

Repeated linear scans instead of building an index

FAQ

When should I use binary search vs a hash table?

Use a hash table when you need fast exact lookups by key and don't care about order — it's O(1) average and the simplest fast option. Use binary search (on sorted data) when you also need ordered operations: range queries ("all values between X and Y"), finding the nearest element, or iterating in order. Binary search is O(log n) vs the hash's O(1), but it supports queries a hash can't. Match the structure to the queries you run.

Why does binary search require sorted data?

Binary search works by eliminating half the remaining elements at each step, which only works if order tells you which half the target must be in. On unsorted data, knowing the middle element is larger than the target tells you nothing about where the target is, so the halving logic is invalid — it returns wrong answers without error. Sorting establishes the invariant binary search depends on; that's why you sort once up front if you'll search repeatedly.

How do databases search millions of rows so fast?

Indexes. Without an index, a query scans every row (O(n)). An index — usually a B-tree — keeps the indexed column in a sorted, balanced structure that supports O(log n) lookups and range scans, so the database jumps to matching rows instead of scanning all of them. It's the same "invest in structure to speed search" principle as binary search, applied to persistent data. The cost is extra storage and slower writes (the index must be maintained). See Database Indexing.

Is linear search ever the right choice?

Yes — for small collections, one-off lookups, or unsorted data where building a structure isn't worth it. If you search a 20-element list once, a linear scan is simpler and the O(n) vs O(1) difference is irrelevant. Linear search also wins when the data changes constantly (no time to maintain a sorted order or index) or when you need to find all matches by a complex predicate. Don't build a hash index for data you'll touch once.