Search algorithm
A search algorithm is an algorithm designed to retrieve information from a data structure or to find a path between states in a problem space. The term encompasses two distinct families of algorithms — those that search data (information retrieval, database queries, pattern matching) and those that search state spaces (pathfinding, game trees, optimization landscapes) — united by a common structure: the traversal of a structured space according to some criterion of relevance or cost.
The two families are rarely taught together, which is a pedagogical failure. A Google search and A* pathfinding are both search algorithms. They differ in their space (web graph vs. grid world), their cost function (relevance vs. distance), and their optimality criteria (precision-recall tradeoffs vs. shortest path). But the underlying mathematics — graph traversal, heuristic guidance, pruning, and tradeoffs between completeness and efficiency — is shared. Understanding search algorithms as a unified family, rather than as isolated techniques for specific domains, clarifies deep connections between information retrieval, artificial intelligence, and network science.
Search on Graphs and Networks
The most basic graph search algorithms are breadth-first search (BFS) and depth-first search (DFS). BFS explores a graph layer by layer from a source node, guaranteeing that the first path found to any node is the shortest path in an unweighted graph. DFS explores as far as possible along each branch before backtracking, using less memory than BFS but providing no path-length guarantees. Both are complete (they will find a target if one exists) and run in time linear in the size of the graph.
For weighted graphs, Dijkstra's algorithm finds the shortest path from a source to all other nodes by maintaining a priority queue of nodes ordered by their current best-known distance. A* search extends Dijkstra with a heuristic function that estimates the remaining cost to the goal, biasing exploration toward promising regions of the graph. When the heuristic is admissible (never overestimates the true cost), A* is both complete and optimal, and with a good heuristic it can be dramatically faster than Dijkstra.
These classical algorithms assume that the graph is fully known and static. In many real-world settings — sensor networks, peer-to-peer systems, social networks — the graph is too large to store locally, too dynamic to cache, or too decentralized to have a global view. Decentralized search addresses this problem by routing queries through local information alone.
Decentralized Search in Networks
The most striking result in decentralized search comes from scale-free and small-world networks. Jon Kleinberg proved that in a network where nodes are arranged on a grid with both local contacts and a small number of random long-range contacts, greedy routing — forwarding a message to the neighbor that is closest to the target — finds short paths in polylogarithmic time, but only if the long-range contacts follow a specific distribution: the probability of a long-range contact at distance \( d \) must be proportional to \( d^{-2} \) in two dimensions (or \( d^{-\alpha} \) with \( \alpha \) equal to the dimension in general). Too many long-range contacts at short distances, and the network lacks the structure to guide search. Too many at long distances, and the local structure is irrelevant.
In real social networks, decentralized search works remarkably well. Stanley Milgram's famous "small-world experiment" showed that letters could be forwarded through chains of acquaintances to reach distant targets in an average of six hops — a result that seemed paradoxical given that no individual has global network knowledge. The resolution is that social networks are structured by geography, occupation, and shared interests, and individuals use these cues to make locally rational forwarding decisions that globally approximate shortest paths.
The degree distribution of a network also constrains search performance. In networks with heavy-tailed degree distributions, hub-based search — forwarding messages to the highest-degree neighbor — can be remarkably efficient. A random walker on a scale-free network will quickly find hubs, and from hubs it can reach any part of the network in few steps. This is the principle behind search engines: the web's link structure is scale-free, and PageRank exploits hub centrality to guide search.
But hub-based search has a dark side. It concentrates traffic on a small number of nodes, creating bottlenecks and vulnerability. If the hub fails, search efficiency collapses. If the hub is compromised, it can censor or manipulate search results. The efficiency of hub-based search is purchased at the cost of centralization risk — a systems-theoretic tradeoff that network designers often ignore.
Search in State Spaces
In artificial intelligence, search algorithms explore state spaces to find sequences of actions that achieve goals. Uninformed search (BFS, DFS, iterative deepening) treats all states as equally promising. Informed search (A*, greedy best-first, beam search) uses domain knowledge to prioritize.
The combinatorial explosion of state spaces — the "curse of dimensionality" — makes exhaustive search intractable for most interesting problems. Chess has approximately \( 10^{120} \) possible games. Protein folding has \( 10^{300} \) possible conformations. The response has been a proliferation of approximate methods: Monte Carlo tree search, which samples the search space stochastically; genetic algorithms, which maintain populations of candidate solutions and evolve them; simulated annealing, which trades off exploration and exploitation through a temperature parameter.
Each of these methods embodies a different answer to the fundamental question of search: how do you allocate finite computational resources across an infinite (or astronomically large) space of possibilities? The answers differ in their assumptions about the structure of the space — whether it is smooth (gradient descent works), multimodal (simulated annealing helps), or discontinuous (evolutionary methods may be necessary). No single method is universal; the choice of search algorithm is itself a decision under uncertainty about the structure of the problem.
Search as a Systems Property
Search is not merely a computational task. It is a systems property that emerges from the coupling between an agent and its environment. A search algorithm is only as good as the structure it searches — and the structure is often shaped by the search itself.
Search engines do not just retrieve information from the web; they reshape the web. Websites optimize for search engine rankings, altering their link structure, content, and architecture to be more discoverable. The search algorithm and the web co-evolve: each shapes the other. This is reflexive search, and it introduces dynamics that static search theory cannot capture. The optimal search algorithm for today's web may be suboptimal for tomorrow's, because today's algorithm will have changed tomorrow's web.
The same reflexivity appears in social networks. Recommender systems suggest connections, and users form connections based on recommendations. The network topology is not an independent structure that search operates on; it is a product of the search process itself. This creates feedback loops that can amplify homophily, create filter bubbles, and concentrate influence in ways that no single search query can account for.
The search algorithm is often taught as a solved problem — a toolbox of techniques with known properties and appropriate use cases. But in complex, evolving systems, search is not a solved problem. It is a co-evolutionary process in which the searcher and the searched mutually construct each other. The question is not "what is the best search algorithm?" but "what kind of world does a given search algorithm create?" — and that is a systems question, not an algorithms question.