Search Algorithms

“Search” covers different problems: locating a value in a sequence, querying an ordered set, looking up a key, or discovering reachable vertices in a graph. Choose the representation before choosing the algorithm.

Decision map

Situation	Method	Typical query cost	Main requirement
One pass over unsorted data	linear search	$O(n)$	equality test
Random-access sorted sequence	binary search	$O(\log n)$	maintained ordering
Exact-key repeated lookup	hash table	expected $O(1)$	hashing and extra space
Ordered dynamic set / ranges	balanced search tree	$O(\log n)$	tree maintenance
Explore deeply / dependency structure	DFS	$O(V+E)$	visited state
Minimum-edge paths in an unweighted graph	BFS	$O(V+E)$	queue and visited state

Costs assume conventional implementations. Hash-table worst cases are not constant, and unbalanced search trees can degrade to linear height.

Amortize preprocessing

Sorting once to enable binary search costs $O(n\log n)$. That investment is useful for many queries or when ordered operations are also needed; it is often wasteful for a single lookup. Likewise, a hash table trades construction and memory for repeated exact-key queries.

Search is often a boundary problem

Binary search generalizes from “find this value” to “find the first position where a monotone predicate becomes true.” DFS and BFS similarly become useful once the output contract is stated: existence, traversal order, parents, distances, components, or a witness path.

Sources

• Open Data Structures
• Python bisect