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.

Account for the whole workload

For a static array and $q$ queries, repeated linear scans cost $O(qn)$. Sorting once and then using binary search costs $O(n\log n+q\log n)$, plus any required copying or preservation of original indexes. Under a unit-cost model this suggests a crossover around a logarithmic number of full-scan queries, not a universal measured threshold. Frequent updates change the calculation: inserting into a sorted array still moves $O(n)$ elements even when bisect finds the position in logarithmic time.

The lookup examples return positions or insertion boundaries; graph traversals instead return reachable vertices and path information. In adjacency lists, $V$ and $E$ count vertices and edges in the portion traversed, not sequence length. A traversal from one source does not cover disconnected components. If the requirement is only existence, early stopping may save work; requesting all reachable vertices or all distances requires completing the traversal.

Sources

• Open Data Structures
• Python bisect

My reading · Opened notes are remembered in this browser.