225:
110:
25:
66:
593:, 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
743:, that are theoretically faster than linear or brute-force search even without the help of data structures or heuristics. While the ideas and applications behind quantum computers are still entirely theoretical, studies have been conducted with algorithms like Grover's that accurately replicate the hypothetical physical versions of quantum computing systems.
653:
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
306:
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
543:, that combine arbitrary heuristics in specific ways. The opposite of local search would be global search methods. This method is applicable when the search space is not limited and all aspects of the given network are available to the entity running the search algorithm.
282:
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
366:: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.
574:. 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 "
953:
López, G V; Gorin, T; Lara, L (26 February 2008). "Simulation of Grover's quantum search algorithm in an Ising-nuclear-spin-chain quantum computer with first- and second-nearest-neighbour couplings".
515:
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
333:, 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.
1145:
654:
discrete optimization; but they are usually formulated and solved in a more abstract setting where the internal representation is not explicitly mentioned.)
84:
1138:
785: – Information filtering system to predict users' preferences, also use statistical methods to rank results in very large data sets
298:
Search algorithms can be classified based on their mechanism of searching into three types of algorithms: linear, binary, and hashing.
307:
defined order. Digital search algorithms work based on the properties of digits in data structures by using numerical keys. Finally,
776:
1131:
1047:
697:
500:
that try to exploit partial knowledge about the structure of this space, such as linear relaxation, constraint generation, and
174:
146:
701:
1392:
153:
1112:
211:
193:
127:
52:
38:
480:, where the goal is to find a set of value assignments to certain variables that will satisfy specific mathematical
637:
The name "combinatorial search" is generally used for algorithms that look for a specific sub-structure of a given
727:
which can be used to find the maximum of a unimodal function and has many other applications in computer science.
160:
1022:
477:
265:
554:, and traverse that tree in some special order. Examples of the latter include the exhaustive methods such as
131:
666:
142:
1323:
1293:
1278:
682:
508:
658:
1402:
1397:
1348:
1222:
1212:
1192:
832:
761: – Special type of computer memory used in certain very-high-speed searching applications hardware
758:
724:
720:
693:
650:
346:
322:, or maximum theoretical run time. Binary search functions, for example, have a maximum complexity of
1227:
788:
642:
447:
407:
272:
563:
370:
319:
885:
1366:
1328:
928:
Hunter, A.H.; Pippenger, Nicholas (4 July 2013). "Local versus global search in channel graphs".
815: – Algorithm that arranges lists in order, necessary for executing certain search algorithms
674:
614:
524:
378:
353:
303:
120:
1172:
678:
622:
861:
167:
1232:
1202:
770:
740:
512:
489:
357:
276:
44:
302:
algorithms check every record for the one associated with a target key in a linear fashion.
1343:
1318:
1263:
972:
764:
638:
610:
575:
559:
488:/ equalities. They are also used when the goal is to find a variable assignment that will
451:
385:
80:
8:
1353:
1338:
1283:
800:
686:
670:
646:
626:
551:
540:
532:
984:
976:
492:
a certain function of those variables. Algorithms for these problems include the basic
1371:
1273:
1268:
1182:
1066:
988:
962:
933:
873:
782:
752:
555:
497:
493:
1333:
1177:
818:
812:
736:
520:
501:
434:
992:
1313:
1298:
1091:
1070:
1056:
980:
571:
516:
395:
363:
241:
1288:
1123:
662:
261:
437:, by changing the parameters of the process (like temperature, pressure, and pH)
1154:
547:
292:
257:
253:
233:
224:
1386:
1303:
1258:
767: – Process that drives self-organization within complex adaptive systems
528:
420:
312:
299:
1253:
1217:
1187:
1096:
1079:
1061:
1042:
1014:
665:
algorithms, for finding specific sub-structures in a given graph — such as
567:
424:
430:
Search engine optimization (SEO) and content optimization for web crawlers
256:. Search algorithms work to retrieve information stored within particular
1207:
1116:
1038:
794:
705:
536:
403:
284:
897:
1197:
1025:. Vol. 3 (2nd ed.). Reading, MA: Addison-Wesley Professional.
717:
696:, that search for patterns within strings. Two famous examples are the
590:
485:
308:
229:
1158:
598:
582:
581:
Another important sub-class consists of algorithms for exploring the
417:
Finding a combination or password from the whole set of possibilities
249:
109:
821: – Software system for finding relevant information on the Web
606:
481:
441:
288:
967:
938:
1308:
1080:"Optimal Bounds for the Predecessor Problem and Related Problems"
1043:"Optimal Bounds for the Predecessor Problem and Related Problems"
618:
602:
496:(also called "naïve" or "uninformed" search), and a variety of
909:
806:
471:
411:
391:
456:
Checking to see if a given value is present in a set of values
594:
586:
1237:
955:
Journal of
Physics B: Atomic, Molecular and Optical Physics
511:
methods, that view the elements of the search space as the
632:
779: – Average solution cost is the same with any method
476:
Algorithms for searching virtual spaces are used in the
410:, choosing the best move to make next (such as with the
823:
Pages displaying short descriptions of redirect targets
711:
849:
657:
An important and extensively studied subclass are the
1078:
Schmittou, Thomas; Schmittou, Faith E. (2002-08-01).
809: – Software for a class of mathematical problems
527:. This category includes a great variety of general
692:
Another important subclass of this category are the
341:
Specific applications of search algorithms include:
336:
275:use search algorithms, they belong to the study of
134:. Unsourced material may be challenged and removed.
1153:
755: – Process of reasoning backwards in sequence
613:— has been extensively studied in the context of
1384:
791: – System to help searching for information
617:. Examples of algorithms for this class are the
927:
952:
85:sources that evaluate within a broader context
1139:
803: – Method for finding kth smallest value
236:that allows for fast retrieval of information
16:Any algorithm which solves the search problem
465:
433:Optimizing an industrial process, such as a
894:, §6.2 ("Searching by Comparison of Keys").
735:There are also search methods designed for
609:strategy planning. This kind of problem —
53:Learn how and when to remove these messages
1146:
1132:
550:, that view the elements as vertices of a
446:Finding the maximum or minimum value in a
1095:
1060:
1036:
966:
937:
855:
673:, circuits, and so on. Examples include
311:directly maps keys to records based on a
212:Learn how and when to remove this message
194:Learn how and when to remove this message
777:No free lunch in search and optimization
730:
318:Algorithms are often evaluated by their
223:
1084:Journal of Computer and System Sciences
1048:Journal of Computer and System Sciences
870:, §6.5 ("Retrieval on Secondary Keys").
633:For sub-structures of a given structure
1385:
704:, and several algorithms based on the
1127:
1013:
915:
903:
891:
879:
867:
562:, as well as various heuristic-based
75:focuses too much on specific examples
773: – Computational search problem
712:Search for the maximum of a function
423:an integer (an important problem in
266:either discrete or continuous values
132:adding citations to reliable sources
103:
59:
18:
13:
930:Networks: An International Journey
585:of multiple-player games, such as
304:Binary, or half-interval, searches
14:
1414:
1105:
546:This class also includes various
337:Applications of search algorithms
34:This article has multiple issues.
882:, §6.1 ("Sequential Searching").
797: – Two-person zero-sum game
108:
64:
23:
1023:The Art of Computer Programming
1002:
478:constraint satisfaction problem
119:needs additional citations for
42:or discuss these issues on the
946:
921:
507:An important subclass are the
1:
985:10.1088/0953-4075/41/5/055504
838:
702:Knuth–Morris–Pratt algorithms
843:
7:
1030:
906:, §6.3 (Digital Searching).
746:
694:string searching algorithms
683:nearest neighbour algorithm
440:Retrieving a record from a
228:Visual representation of a
10:
1419:
1393:Internet search algorithms
833:Category:Search algorithms
759:Content-addressable memory
651:combinatorial optimization
469:
460:
347:combinatorial optimization
264:of a problem domain, with
1362:
1246:
1165:
1113:Uninformed Search Project
789:Search engine (computing)
466:For virtual search spaces
408:combinatorial game theory
1007:
371:nurse scheduling problem
320:computational complexity
1367:List of data structures
649:, and so on. The term
615:artificial intelligence
379:constraint satisfaction
354:vehicle routing problem
260:, or calculated in the
1097:10.1006/jcss.2002.1822
1062:10.1006/jcss.2002.1822
548:tree search algorithms
502:constraint propagation
237:
1019:Sorting and Searching
856:Beame & Fich 2002
771:Linear search problem
731:For quantum computers
641:, such as a graph, a
358:shortest path problem
277:information retrieval
227:
1264:Breadth-first search
765:Dual-phase evolution
675:Dijkstra's algorithm
611:combinatorial search
560:breadth-first search
490:maximize or minimize
386:map coloring problem
279:, not algorithmics.
252:designed to solve a
128:improve this article
81:improve this article
1354:Topological sorting
1284:Dynamic programming
977:2008JPhB...41e5504L
801:Selection algorithm
679:Kruskal's algorithm
564:search tree pruning
541:genetic programming
533:simulated annealing
523:criterion, or in a
1372:List of algorithms
1279:Divide and conquer
1274:Depth-first search
1269:Brute-force search
1183:Binary search tree
918:, §6.4, (Hashing).
783:Recommender system
753:Backward induction
741:Grover's algorithm
716:In 1953, American
639:discrete structure
629:and its variants.
623:alpha–beta pruning
556:depth-first search
494:brute-force search
238:
143:"Search algorithm"
1403:Search algorithms
1398:Ranking functions
1380:
1379:
1178:Associative array
819:Web search engine
813:Sorting algorithm
737:quantum computers
619:minimax algorithm
531:methods, such as
525:stochastic search
435:chemical reaction
222:
221:
214:
204:
203:
196:
178:
102:
101:
57:
1410:
1349:String-searching
1148:
1141:
1134:
1125:
1124:
1101:
1099:
1074:
1064:
1026:
997:
996:
970:
950:
944:
943:
941:
925:
919:
913:
907:
901:
895:
889:
883:
877:
871:
865:
859:
853:
824:
725:Fibonacci search
708:data structure.
687:Prim's algorithm
661:, in particular
659:graph algorithms
572:branch and bound
566:methods such as
517:steepest descent
396:crossword puzzle
364:knapsack problem
332:
293:database indexes
246:search algorithm
242:computer science
217:
210:
199:
192:
188:
185:
179:
177:
136:
112:
104:
97:
94:
88:
68:
67:
60:
49:
27:
26:
19:
1418:
1417:
1413:
1412:
1411:
1409:
1408:
1407:
1383:
1382:
1381:
1376:
1358:
1289:Graph traversal
1242:
1166:Data structures
1161:
1155:Data structures
1152:
1122:
1108:
1077:
1041:(August 2002).
1033:
1010:
1005:
1000:
951:
947:
926:
922:
914:
910:
902:
898:
890:
886:
878:
874:
866:
862:
854:
850:
846:
841:
822:
749:
733:
714:
663:graph traversal
635:
597:guidance or in
539:, A-teams, and
474:
468:
463:
406:and especially
339:
323:
218:
207:
206:
205:
200:
189:
183:
180:
137:
135:
125:
113:
98:
92:
89:
78:
69:
65:
28:
24:
17:
12:
11:
5:
1416:
1406:
1405:
1400:
1395:
1378:
1377:
1375:
1374:
1369:
1363:
1360:
1359:
1357:
1356:
1351:
1346:
1341:
1336:
1331:
1326:
1321:
1316:
1311:
1306:
1301:
1296:
1291:
1286:
1281:
1276:
1271:
1266:
1261:
1256:
1250:
1248:
1244:
1243:
1241:
1240:
1235:
1230:
1225:
1220:
1215:
1210:
1205:
1200:
1195:
1190:
1185:
1180:
1175:
1169:
1167:
1163:
1162:
1151:
1150:
1143:
1136:
1128:
1121:
1120:
1109:
1107:
1106:External links
1104:
1103:
1102:
1075:
1032:
1029:
1028:
1027:
1009:
1006:
1004:
1001:
999:
998:
945:
920:
908:
896:
884:
872:
860:
847:
845:
842:
840:
837:
836:
835:
826:
825:
816:
810:
804:
798:
792:
786:
780:
774:
768:
762:
756:
748:
745:
732:
729:
713:
710:
634:
631:
467:
464:
462:
459:
458:
457:
454:
444:
438:
431:
428:
418:
415:
400:
399:
398:
388:
375:
374:
373:
367:
360:
338:
335:
273:search engines
258:data structure
254:search problem
234:data structure
220:
219:
202:
201:
116:
114:
107:
100:
99:
72:
70:
63:
58:
32:
31:
29:
22:
15:
9:
6:
4:
3:
2:
1415:
1404:
1401:
1399:
1396:
1394:
1391:
1390:
1388:
1373:
1370:
1368:
1365:
1364:
1361:
1355:
1352:
1350:
1347:
1345:
1342:
1340:
1337:
1335:
1332:
1330:
1327:
1325:
1322:
1320:
1317:
1315:
1312:
1310:
1307:
1305:
1304:Hash function
1302:
1300:
1297:
1295:
1292:
1290:
1287:
1285:
1282:
1280:
1277:
1275:
1272:
1270:
1267:
1265:
1262:
1260:
1259:Binary search
1257:
1255:
1252:
1251:
1249:
1245:
1239:
1236:
1234:
1231:
1229:
1226:
1224:
1221:
1219:
1216:
1214:
1211:
1209:
1206:
1204:
1201:
1199:
1196:
1194:
1191:
1189:
1186:
1184:
1181:
1179:
1176:
1174:
1171:
1170:
1168:
1164:
1160:
1156:
1149:
1144:
1142:
1137:
1135:
1130:
1129:
1126:
1118:
1114:
1111:
1110:
1098:
1093:
1089:
1085:
1081:
1076:
1072:
1068:
1063:
1058:
1054:
1050:
1049:
1044:
1040:
1037:Beame, Paul;
1035:
1034:
1024:
1020:
1016:
1015:Knuth, Donald
1012:
1011:
994:
990:
986:
982:
978:
974:
969:
964:
961:(5): 055504.
960:
956:
949:
940:
935:
931:
924:
917:
912:
905:
900:
893:
888:
881:
876:
869:
864:
858:, p. 39.
857:
852:
848:
834:
831:
830:
829:
820:
817:
814:
811:
808:
805:
802:
799:
796:
793:
790:
787:
784:
781:
778:
775:
772:
769:
766:
763:
760:
757:
754:
751:
750:
744:
742:
738:
728:
726:
722:
719:
709:
707:
703:
699:
695:
690:
688:
684:
680:
676:
672:
668:
664:
660:
655:
652:
648:
644:
640:
630:
628:
624:
620:
616:
612:
608:
604:
600:
596:
592:
588:
584:
579:
577:
573:
569:
565:
561:
557:
553:
549:
544:
542:
538:
534:
530:
529:metaheuristic
526:
522:
518:
514:
510:
505:
503:
499:
495:
491:
487:
483:
479:
473:
455:
453:
449:
445:
443:
439:
436:
432:
429:
426:
422:
419:
416:
413:
409:
405:
401:
397:
393:
390:Filling in a
389:
387:
383:
382:
380:
376:
372:
368:
365:
361:
359:
355:
351:
350:
348:
344:
343:
342:
334:
330:
326:
321:
316:
314:
313:hash function
310:
305:
301:
300:Linear search
296:
294:
290:
286:
280:
278:
274:
269:
267:
263:
259:
255:
251:
247:
243:
235:
231:
226:
216:
213:
198:
195:
187:
176:
173:
169:
166:
162:
159:
155:
152:
148:
145: –
144:
140:
139:Find sources:
133:
129:
123:
122:
117:This article
115:
111:
106:
105:
96:
93:December 2014
86:
82:
76:
73:This article
71:
62:
61:
56:
54:
47:
46:
41:
40:
35:
30:
21:
20:
1329:Root-finding
1254:Backtracking
1218:Segment tree
1188:Fenwick tree
1090:(1): 38–72.
1087:
1083:
1055:(1): 38–72.
1052:
1046:
1018:
1003:Bibliography
958:
954:
948:
929:
923:
911:
899:
887:
875:
863:
851:
828:Categories:
827:
734:
718:statistician
715:
691:
656:
636:
627:A* algorithm
580:
576:completeness
568:backtracking
545:
509:local search
506:
475:
425:cryptography
377:Problems in
356:, a form of
345:Problems in
340:
328:
324:
317:
297:
285:search trees
281:
270:
262:search space
245:
239:
208:
190:
181:
171:
164:
157:
150:
138:
126:Please help
121:verification
118:
90:
79:Please help
74:
50:
43:
37:
36:Please help
33:
1208:Linked list
1117:Wikiversity
1039:Fich, Faith
795:Search game
721:Jack Kiefer
706:suffix tree
698:Boyer–Moore
645:, a finite
537:tabu search
486:inequations
404:game theory
381:, such as:
349:, such as:
1387:Categories
1344:Sweep line
1319:Randomized
1247:Algorithms
1198:Hash table
1159:algorithms
916:Knuth 1998
904:Knuth 1998
892:Knuth 1998
880:Knuth 1998
868:Knuth 1998
839:References
625:, and the
591:backgammon
521:best-first
498:heuristics
470:See also:
414:algorithm)
230:hash table
184:April 2016
154:newspapers
83:by adding
39:improve it
1339:Streaming
1324:Recursion
968:0710.3196
939:1004.2526
844:Citations
667:subgraphs
603:financial
599:marketing
583:game tree
482:equations
421:Factoring
289:hash maps
271:Although
250:algorithm
45:talk page
1031:Articles
1017:(1998).
993:18796310
747:See also
723:devised
607:military
513:vertices
442:database
1334:Sorting
1309:Minimax
1115:at the
1071:1991980
973:Bibcode
739:, like
461:Classes
309:hashing
168:scholar
1314:Online
1299:Greedy
1228:String
1069:
991:
807:Solver
685:, and
681:, the
643:string
472:Solver
412:minmax
392:sudoku
291:, and
248:is an
170:
163:
156:
149:
141:
1223:Stack
1213:Queue
1193:Graph
1173:Array
1067:S2CID
1008:Books
989:S2CID
963:arXiv
934:arXiv
671:paths
647:group
605:, or
595:robot
587:chess
452:array
327:(log
175:JSTOR
161:books
1294:Fold
1238:Trie
1233:Tree
1203:Heap
1157:and
700:and
570:and
558:and
552:tree
484:and
448:list
384:The
369:The
362:The
352:The
244:, a
232:, a
147:news
1092:doi
1057:doi
981:doi
589:or
578:".
519:or
450:or
402:In
394:or
240:In
130:by
1389::
1088:65
1086:.
1082:.
1065:.
1053:65
1051:.
1045:.
1021:.
987:.
979:.
971:.
959:41
957:.
932:.
689:.
677:,
669:,
621:,
601:,
535:,
504:.
315:.
295:.
287:,
268:.
48:.
1147:e
1140:t
1133:v
1119:.
1100:.
1094::
1073:.
1059::
995:.
983::
975::
965::
942:.
936::
427:)
331:)
329:n
325:O
215:)
209:(
197:)
191:(
186:)
182:(
172:·
165:·
158:·
151:·
124:.
95:)
91:(
87:.
77:.
55:)
51:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
