Search algorithm - wikipedia Search algorithm This article has multiple issues. Please help improve it or discuss these issues on the talk page. ( Learn how and when to remove these template messages ) This article needs attention from an expert in computer science. The specific problem is : longstanding subpar state of article structure and content, which is currently list based, dated, and non-encyclopedic, and without external sourcing. See the talk page for details. WikiProject Computer science may be able to help recruit an expert. ( December 2014 ) This article focuses too much on specific examples without explaining their importance to its main subject. Please help improve this article by citing reliable, secondary sources that evaluate and synthesize these or similar examples within a broader context. ( December 2014 ) This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. ( April 2016 ) Visual representation of a hash table, a data structure that allows for fast retrieval of information. In computer science, a search algorithm is any algorithm which solves the Search problem, namely, to retrieve information stored within some data structure, or calculated in the search space of a problem domain. Examples of such structures include but are not limited to a Linked List, an Array data structure, or a Search tree. The appropriate search algorithm often depends on the data structure being searched, and may also include prior knowledge about the data. Searching also encompasses algorithms that query the data structure, such as the SQL SELECT command. Search algorithms can be classified based on their mechanism of searching. 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 that use numerical keys. Finally, hashing directly maps keys to records based on a hash function. Searches outside a linear search require that the data be sorted in some way. Search functions are also evaluated on the basis of their complexity, or maximum theoretical run time. Binary search functions, for example, have a maximum complexity of O ( log n ), or logarithmic time. This means that the maximum number of operations needed to find the search target is a logarithmic function of the size of the search space. Contents 1 Classes 1.1 For virtual search spaces 1.2 For sub-structures of a given structure 1.3 Search for the maximum of a function 1.4 For quantum computers 2 See also 3 References 3.1 Citations 3.2 Bibliography 3.2. 1 Books 3.2. 2 Articles 4 External links Classes For virtual search spaces See also : Solver Algorithms for searching virtual spaces are used in the constraint satisfaction problem, where the goal is to find a set of value assignments to certain variables that will satisfy specific mathematical equations and inequations / equalities. They are also used when the goal is to find a variable assignment that will maximize or minimize a certain function of those variables. Algorithms for these problems include the basic brute - force search ( also called `` naïve '' or `` uninformed '' search ), and a variety of heuristics that try to exploit partial knowledge about the structure of this space, such as linear relaxation, constraint generation, and constraint propagation. An important subclass are the local search methods, that view the elements of the search space as the vertices of a graph, with edges defined by a set of heuristics applicable to the case ; and scan the space by moving from item to item along the edges, for example according to the steepest descent or best - first criterion, or in a stochastic search. This category includes a great variety of general metaheuristic methods, such as simulated annealing, tabu search, A-teams, and genetic programming, that combine arbitrary heuristics in specific ways. This class also includes various tree search algorithms, that view the elements as vertices of a tree, and traverse that tree in some special order. Examples of the latter include the exhaustive methods such as depth - first search and breadth - first search, as well as various heuristic - based search tree pruning methods such as backtracking and branch and bound. Unlike general metaheuristics, which at best work only in a probabilistic sense, many of these tree - search methods are guaranteed to find the exact or optimal solution, if given enough time. This is called `` completeness ''. Another important sub-class consists of algorithms for exploring the game tree of multiple - player games, such as chess or backgammon, whose nodes consist of all possible game situations that could result from the current situation. The goal in these problems is to find the move that provides the best chance of a win, taking into account all possible moves of the opponent ( s ). Similar problems occur when humans or machines have to make successive decisions whose outcomes are not entirely under one 's control, such as in robot guidance or in marketing, financial, or military strategy planning. This kind of problem -- combinatorial search -- has been extensively studied in the context of artificial intelligence. Examples of algorithms for this class are the minimax algorithm, alpha -- beta pruning, * Informational search and the A * algorithm. For sub-structures of a given structure The name `` combinatorial search '' is generally used for algorithms that look for a specific sub-structure of a given discrete structure, such as a graph, a string, a finite group, and so on. The term combinatorial optimization is typically used when the goal is to find a sub-structure with a maximum ( or minimum ) value of some parameter. ( Since the sub-structure is usually represented in the computer by a set of integer variables with constraints, these problems can be viewed as special cases of constraint satisfaction or discrete optimization ; but they are usually formulated and solved in a more abstract setting where the internal representation is not explicitly mentioned. ) An important and extensively studied subclass are the graph algorithms, in particular graph traversal algorithms, for finding specific sub-structures in a given graph -- such as subgraphs, paths, circuits, and so on. Examples include Dijkstra 's algorithm, Kruskal 's algorithm, the nearest neighbour algorithm, and Prim 's algorithm. Another important subclass of this category are the string searching algorithms, that search for patterns within strings. Two famous examples are the Boyer -- Moore and Knuth -- Morris -- Pratt algorithms, and several algorithms based on the suffix tree data structure. Search for the maximum of a function In 1953, American statistician Jack Kiefer devised Fibonacci search which can be used to find the maximum of a unimodal function and has many other applications in computer science. For quantum computers There are also search methods designed for quantum computers, like Grover 's algorithm, that are theoretically faster than linear or brute - force search even without the help of data structures or heuristics. See also Category : Search algorithms Backward induction Content - addressable memory hardware Dual - phase evolution Linear search problem No free lunch in search and optimization Recommender systems also use statistical methods to rank results in very large data sets Search engine ( computing ) Search game Selection algorithm Solver Sorting algorithms necessary for executing certain search algorithms Web search engine References Citations Jump up ^ Beame & Fich 2002, p. 39. Jump up ^ Knuth 1998, § 6.5 ( `` Retrieval on Secondary Keys '' ). Jump up ^ Knuth 1998, § 6.1 ( `` Sequential Searching '' ). Jump up ^ Knuth 1998, § 6.2 ( `` Searching by Comparison of Keys '' ). Jump up ^ Knuth 1998, § 6.3 ( Digital Searching ). Jump up ^ Knuth 1998, § 6.4, ( Hashing ). Jump up ^ Kagan E. and Ben - Gal I. ( 2014 ). `` A Group - Testing Algorithm with Online Informational Learning '' ( PDF ). IIE Transactions, 46 : 2, 164 - 184,. Bibliography Books Knuth, Donald ( 1998 ). Sorting and Searching. The Art of Computer Programming. 3 ( 2nd ed. ). Reading, MA : Addison - Wesley Professional. Articles Beame, Paul ; Fich, Faith E. ( 2002 - 08 - 01 ). `` Optimal Bounds for the Predecessor Problem and Related Problems ''. Journal of Computer and System Sciences. 65 ( 1 ) : 38 -- 72. doi : 10.1006 / jcss. 2002.1822. External links Uninformed Search Project at the Wikiversity. Unsorted Data Searching Using Modulated Database. Computer Shortcuts General Shortcuts Control - A Select All Control - B Bold -- Face Font Control - C Copy Control - F Find Control - I Italics Control - N New... Control - O Open... Control - P Print Control - Q Quit Control - S Save Control - U Underline Control - V Paste Control - X Cut Control - Y Redo Control - Z Undo Alt + F4 Quit F1 Help File Tab Indent Special Internet Shortcuts Control - D Add to Favorites Control - E Search Control - F Favorites Control - H History Control - Shift - W Close Programs and Return to Desktop Backspace Last Page Viewed Esc Stop F5 Refresh Current Page F11 Full Screen Retrieved from `` https://en.wikipedia.org/w/index.php?title=Search_algorithm&oldid=814113198 '' Categories : Search algorithms Hidden categories : Articles needing expert attention from December 2014 All articles needing expert attention Computer science articles needing expert attention Wikipedia articles needing context from December 2014 Articles needing additional references from April 2016 All articles needing additional references Articles with multiple maintenance issues Talk Search Contents About Wikipedia Azərbaycanca বাংলা Български Dansk Deutsch Ελληνικά Español فارسی Français Bahasa Indonesia Interlingua Italiano עברית Magyar Nederlands 日本 語 Português Српски / srpski Suomi ไทย Türkçe Українська Tiếng Việt Edit links This page was last edited on 6 December 2017, at 23 : 30. Text is available under the Creative Commons Attribution - ShareAlike License ; additional terms may apply. By using this site, you agree to the Terms of Use and Privacy Policy. Wikipedia ® is a registered trademark of the Wikimedia Foundation, Inc., a non-profit organization. About Wikipedia

Question: which search uses only the linear space for searching
Answer: Linear search algorithms