Method
Search algorithm
Overview
In computer science, a search algorithm is an algorithm designed to solve a search problem. Search algorithms work to retrieve information stored within particular data structure, or calculated in the search space of a problem domain, with either discrete or continuous values.
Although search engines use search algorithms, they belong to the study of information retrieval, not algorithmics.
The appropriate search algorithm to use often depends on the data structure being searched, and may also include prior knowledge about the data. Search algorithms can be made faster or more efficient by specially constructed database structures, such as search trees, hash maps, and database indexes.
Search algorithms can be classified based on their mechanism of searching into three types of algorithms: linear, binary, and hashing. Linear search algorithms check every record for the one associated with a target key in a linear fashion. Binary, or half-interval, searches repeatedly target the center of the search structure and divide the search space in half. Comparison search algorithms improve on linear searching by successively eliminating records based on comparisons of the keys until the target record is found, and can be applied on data structures with a defined order. Digital search algorithms work based on the properties of digits in data structures by using numerical keys. Finally, hashing directly maps keys to records based on a hash function.
Algorithms are often evaluated by their computational complexity, or maximum theoretical run time. Binary search functions, for example, have a maximum complexity of O(log n), or logarithmic time. In simple terms, the maximum number of operations needed to find the search target is a logarithmic function of the size of the search space.
Overview adapted from Wikipedia (CC BY-SA 4.0; see the article history for authors).
Possible passages
Found by search and not yet checked by a person; they may only mention the idea in passing.
FLEISCHHAUER proceeded to describe various search and retrieval capabilities while ERWAY worked the computer. In this particular package the "go to" pull-down allowed the user in effect to jump out of Toolbook, where the interactive program was located, and enter the third-party software used by AM for this text collection,…
Library of Congress, Workshop on Electronic Texts
States what Search algorithm is.
This is nothing else than the necessity of abstract logic, which is the presupposition involved in the very fact of interrelated existence as disclosed in each immediate occasion of experience. The key to the pattern means this fact:—that from a select set of those general conditions, exemplified in any one and the same occasion, a pattern involving an infinite variety of other such conditions, also exemplified in…
Alfred North Whitehead, Science and the modern world
States what Search algorithm is.
The arbitrarily large event with which the series starts has no importance at all. We can arbitrarily exclude any set of events at the big end of an abstractive set without the loss of any important property to the set as thus modified. I call the limiting character of natural relations which is indicated by an abstractive set, the 'intrinsic character' of the set; also the properties, connected with the relation of…
Alfred North Whitehead, The Concept of Nature The Tarner Lectures Delivered in Trinity College, November 1919
States what Search algorithm is.
Related ideas
- Artificial intelligence
- Game theory
- Statistics
- Completeness (logic)
- Chess
- Computer science
- Computational complexity
- Algorithm
- Military
- Heuristic (computer science)
Place in the tradition
Part of First-order logic.