Search Comparison

Linear · Binary · Hash · Graph

1:00

A head-to-head comparison of linear, binary, hash, and graph search — their complexities, preconditions, pitfalls, and when to use each.

By the end, you can

State the time complexity and data precondition for each of the four search methods.
Apply the four-step decision procedure to choose the right search for a given scenario.
Explain why hash lookup is O(1) on average but not in the worst case.
Distinguish the question BFS/DFS answers (reachability/paths) from the question linear/binary/hash answer (membership).
Identify why the naive midpoint formula `(lo + hi) / 2` can overflow in fixed-width integer languages and write the safe alternative.
Recognize the three pitfalls in the binary-search family and the three in the hash/graph family.
Map real-world systems (database indexes, dictionaries, GPS routers, log scanners) to the search strategy they use.

Up next in Searching & Sorting