Search algorithm
A search algorithm is a procedure for locating data in a structure or space. This article surveys common techniques, their requirements, performance trade-offs, and typical applications.
A search algorithm is any systematic method for locating a target element, value, path, or pattern within a collection, structure, or abstract space. The term covers simple procedures that examine items one by one and sophisticated methods that exploit order, indexing, hashing, or domain knowledge to avoid inspecting every element. Search algorithms are fundamental in computer science and appear across databases, information retrieval, graph theory, artificial intelligence, and everyday software.
Basic categories and examples
Common categories include:
- Linear search: inspects each element in sequence; simple and requires no extra structure but is O(n) in time for n items.
- Binary and other divide-and-conquer searches: operate on sorted collections and reduce the remaining search space rapidly (logarithmic behaviour when random access is available).
- Hash-based lookup: uses a hash function to map keys to buckets, often giving average constant-time lookup in practice; see hash tables.
- Tree and index searches: range queries and ordered lookup on balanced trees or database indexes.
Search in graphs and AI
When the domain is a network of nodes and edges, search finds paths or reachable states. Breadth-first search (BFS) and depth-first search (DFS) are standard for unweighted graphs; Dijkstra's algorithm and A* extend these ideas to weighted or heuristic-guided searches. In artificial intelligence and planning, heuristic and approximate searches trade completeness for speed, enabling solutions in very large or continuous spaces.
Performance, trade-offs and requirements
Different techniques assume different preconditions: sorted data, random access, or available memory for auxiliary structures. Key trade-offs include time versus space (indexes and caches speed queries at the cost of memory), preprocessing time versus query time (building an index or hash table speeds later lookups), and average-case versus worst-case guarantees. Many search methods are analyzed using Big-O notation to express how cost grows with input size.
Applications and notable facts
Search algorithms power database queries, web search, spell checking, routing, genome sequence matching, and real-time path planning in robotics and games. They differ from sorting algorithms, though the two often interact: sorted data enables faster comparison-based searches. Practical implementations must also consider concurrency, distribution, and fault tolerance in large-scale systems.
Understanding the structure of the data and the expected query patterns is essential when choosing a search method: a simple linear scan may suffice for tiny collections, while large-scale systems usually rely on indexing, hashing, or specialized graph search strategies to achieve acceptable performance.
Simple search algorithms
Simple search algorithms neglect the specific nature of the problem at hand. Therefore, they can be implemented more generally and abstractly, allowing the same implementation to be used for a wide range of problems. The disadvantage of simple search algorithms is the cost incurred: The search space of search problems is generally very large, but simple search only runs in small search spaces in acceptable time.
Search in lists
Algorithms for searching in lists are the simplest search algorithms of all. The goal of searching in lists is to find a particular element of a list of which the associated search key is known. Since this problem is often encountered in computer science, the algorithms used - as well as their complexity - are very well studied.
The simplest search algorithm for lists is the linear search. It traverses one element after the other until an element with the searched key is encountered. The linear search has a running time of 
(n is the number of elements in the list) and can be applied to both sorted and unsorted lists. An advanced method is binary search with a running time of 
. For large lists, it is much more efficient than linear search, but it assumes that the list has been sorted beforehand and that random access to the elements is possible. Interpolation search, also called interval search, is an improvement on binary search that assumes the data is uniformly distributed. The running time 
is better than that of binary search only for very large data sets. Another search algorithm for lists is the Grover algorithm, which is used on quantum computers and runs quadratically faster than classical linear search for unsorted lists. Hashing can also be used for list searching, which takes a constant time average. 
but takes linear time in the worst case.
Search in trees
Searching in trees is the supreme discipline among search algorithms. It searches nodes of trees, regardless of whether the tree is explicit or implicit (generated during the search). The following principle is applied: A node is taken from a data structure. Its child nodes are examined and, if necessary, added to the data structure. Depending on the selection of the data structure, the tree can be searched in different orders. Using a queue leads to a breadth-first search in which the tree is traversed level by level. When using a stack, on the other hand, the system searches up to one leaf at a time and only then continues with the next child node. This is called a depth-first search.
Search in graphs
Many problems in graph theory can be solved using search algorithms. Examples of these problems are the traveling salesman problem, the computation of shortest paths, and the construction of a minimal spanning tree. The corresponding algorithms are for example Kruskal's algorithm, Dijkstra's algorithm or Prim's algorithm, which can be seen as extensions of the algorithms for searching trees.
Heuristic (Informed) search algorithms
Strategies that can speed up the process of finding solutions are called heuristics. Typical heuristics are rules of thumb, orientation on examples, and emulation of the human problem-solving process. Accordingly, procedures can be divided into uninformed (also called blind search) and informed (use of heuristics). The study of different methods for heuristic search, the development and implementation of new methods and their application to different problem areas are usually counted as the algorithmic core of artificial intelligence. This includes, for example, automatic reasoning, the control of robots and, as typical representatives, especially games. This includes two-person games (zero-sum games with complete information) such as chess, checkers, and mills, as well as one-person games such as sliding puzzles or solitaire. The classical methods for heuristic search are A*, IDA*, bidirectional search schemes, the minimax method, alpha-beta search.
Heuristic search algorithms are also used when an algorithm for solving a problem is too computationally intensive. In this case, a certain error is accepted - i.e. a non-optimal solution is also accepted - if the computing time used can be significantly reduced in return.
Questions and answers
Q: What is a search algorithm?
A: A search algorithm is a method for finding a target value within a list.
Q: How does a search algorithm work?
A: A search algorithm checks each element of the list for the target value until a match is found or until all the elements have been searched.
Q: Is linear search practical?
A: Linear search is rarely practical because other search algorithms and schemes allow faster searching for all but short lists.
Q: What are some other search algorithms besides linear search?
A: Some other search algorithms are binary search algorithm and hash tables.
Q: Are other search algorithms faster than linear search?
A: Yes, other search algorithms like binary search algorithm and hash tables are significantly faster than linear search for all but short lists.
Q: Why is linear search not the ideal search algorithm?
A: Linear search is not the ideal search algorithm because other search algorithms and schemes allow significantly faster searching for all but short lists.
Q: What is binary search algorithm?
A: Binary search algorithm is a search algorithm that works by repeatedly dividing the search interval in half until the target value is found or until it is confirmed that the target value is not in the list.
Related articles
Author
AlegsaOnline.com Search algorithm Leandro Alegsa
URL: https://en.alegsaonline.com/art/88337