Compare every search
Ordered arrays, hash tables, trees, tries, and graphs — click any column to sort, click a row to open the algorithm.
| Algorithm | Dataset | Best | Average ↑ | Worst | Memory | Needs sorted | Typical usage |
|---|---|---|---|---|---|---|---|
| Hash Lookup | Hash table | O(1) | O(1) | O(n) | O(n) | — | You need pure equality lookups (dicts, caches, sets, dedup) and don't care about key order. |
| Interpolation Search | Sorted array | O(1) | O(log log n) | O(n) | O(1) | yes | Large sorted arrays of uniformly distributed numeric keys — IDs, timestamps, evenly sampled readings. |
| Binary Search | Sorted array | O(1) | O(log n) | O(log n) | O(1) | yes | Data is sorted (or sortable once) and read-heavy, or the problem has a monotonic yes/no boundary. |
| Binary Search Tree Search | Binary search tree | O(1) | O(log n) | O(n) | O(1) | — | You need a mutable collection with ordered operations — range queries, floor/ceiling, sorted iteration — alongside log-time search. |
| Exponential Search | Sorted array | O(1) | O(log i) | O(log i) | O(1) | yes | Length is unknown/unbounded, or targets cluster near the front of a large sorted sequence. |
| Trie Search | Trie | O(1) | O(m) | O(m) | O(alphabet · nodes) | — | Queries are prefix-shaped — autocomplete, longest-prefix match, lexicographic enumeration — or keys share heavy prefixes. |
| Jump Search | Sorted array | O(1) | O(√n) | O(√n) | O(1) | yes | Sorted data where seeks or backward moves are expensive, or iteration is forward-only with checkpoints. |
| Breadth-First Search (BFS) | Graph | O(1) | O(V + E) | O(V + E) | O(V) | — | You need shortest/fewest-hops answers, level-order structure, or nearest-first exploration on an unweighted graph. |
| Depth-First Search (DFS) | Graph | O(1) | O(V + E) | O(V + E) | O(V) | — | You need exhaustive exploration, backtracking, topological order, cycle detection, or components — and path length doesn't matter. |
| Linear Search | Array | O(1) | O(n) | O(n) | O(1) | — | Data is small, unsorted, queried once, or only reachable sequentially. |