200:
579:
331:
254:
603:
233:
191:
1039:
that particular set to attain adequate performance. In other words, a tree search is not mutually exclusive with any other search technique that may be used for specific sets. It is a method of reducing the number of relevant items to be searched to those within certain branches of the tree, thus reducing running time. For example, the
1038:
The efficiency of a tree search is highly dependent upon the number and structure of nodes in relation to the number of items on that node. If there are a large number of items on one or more nodes, there may well be a requirement to use a specific different search technique for locating items within
851:
The topic "search algorithm" is too vast to discuss in detail in a single article, so I have reorganized it into an overview of the major classes of search problems and algorithms, with only a few *examples* of each class. Detailed discussions, such as complexity or applications, are best left to the
1141:
There exists a wide expanse of algorithm and discussion on wikipedia. But it's difficult to find a lot of them without finding them first on some other discussion site. Therefore, I suggest (and I'm doing it here since I could not get to the 'talk' section of 'algorithm' page on wikipedia) that we
872:
Lists, and sequences generally, are perhaps the most commonly encountered data structures; search algorithms adapted for them are common as well. The goal is to find one element of a set (i.e., from the list) by some criterion (typically called a key and perhaps containing other information related
762:
The mention of Grover's
Algorithm, and quantum computing is somewhat misleading. It states that Grover's algorithm 'provides a solution' in polynomial time. It does no such thing: It is a theoretical model of a non-existant computing system. Maybe some day there will be quantum computers, but until
1173:
This article is stalled at a level of expertise and degree of quality of organization and sourcing that is markedly subpar, and so I have called for expert attention. The article has for some time been essentially a hodgepodge listing of various ideas and approaches in the subject area, strung
1177:
As well, the only source currently listed, Knuth (at
Stanford, reference to which I completed today, to make fully accessible)--while a fine starting point--does not appear anywhere as an inline citation, and is, at this point in time, over 15 years old. This, I would note, is a significant
1150:
You get the idea. This way, if people are wanting to discover what's new or what's old, where we've been and where things are going, or just want to endulge themselves in algorithms and computer techniques, they can just start at one of these pages and work their way down to more detailed
352:
1043:
telephone directory may contain entries for 20,000+ people whose surname is 'Smith' belonging on a tree branch on which are found 'surnames beginning S'. The list of names may, or may not be, further ordered (ie, structured) by subscribers first names or initials. A
1181:
Bottom line, the article needs to be re-structured by an expert, with standard contemporary academic sources added, with much of the extraneous linked material removed, so that it is a stand-alone, substantive encyclopedia article useful to a lay-reader.
971:
Most list search algorithms, such as linear search, binary search, and self-balancing binary search trees, can be extended with little additional cost to find all values less than or greater than a given key, an operation called
615:
746:
Combinatorial Search
Algorithms are a subset of Search Algorithms; Combinatorial Search could refer to the search problem rather than the algorithm used to solve it. The two articles should not be merged or directly linked.
153:
376:
1225:
516:
1151:
discussions from there. These should all go back to the 'algorithm' page on wikipedia, as a starting point. 'See also' at the bottom of course can still link to related topics....
898:
is the number of items in the list. It can be used directly on any unprocessed list, regardless of history, which is sometimes useful. A more sophisticated list search algorithm is
1250:
433:
371:
1005:, its successors examined and added to the data structure. By manipulating the data structure, the tree can be explored in different orders. For instance, level by level (ie,
304:
1215:
1230:
147:
1240:
294:
204:
1245:
1235:
270:
79:
1210:
1220:
914:
for large lists, but is sometimes useful for surprisingly small ones given its increase in speed. But it requires the list be sorted before searching (see
478:
627:
317:
261:
238:
44:
85:
699:
This is the wrong page to ask about
Knowledge (XXG)'s search engine; this talk page is for discussing improvements to the Knowledge (XXG) article
452:
1018:
962:) time. Such tree searches can be seen as extending the ideas of binary search to allow fast insertion and removal in the data structures. See
424:
541:
586:
787:
30:
405:
890:, which examines each element of the list as they are encountered. It is expensive in running time compared to many other algorithms: in
1205:
1122:
1155:
99:
955:
854:
The material that could not be used is temproarily copied below. It should be merged eventually into the relevant articles, such as
104:
20:
954:)) In addition, more space and time is required to set up such tables. Another search based on specialized data structures uses
74:
497:
168:
997:, whether the tree is explicit or implicit (ie, generated by the search algorithm's execution). The basic principle is that a
462:
343:
213:
680:
135:
386:
65:
1142:
collect all the algorithms we have on here, and make them hierarchical by category. What I mean is, Algorithm page -: -->
1075:
is an online (i.e. sequentially presented) search problem with imperfect information, and a statistically optimal strategy
1067:
507:
269:
related articles on
Knowledge (XXG). If you would like to participate, please visit the project page, where you can join
1143:
sub-topics: search algorithms, sorting algorithms, graph algorithms, generic algorithms, etc. Generic
Algorithms -: -->
472:
1154:
Just a suggestion that would make wikipedia's algorithms arsenal more efficient to find and search/browse through...
129:
109:
1084:
726:
703:. If the question is about a local copy of Mediawiki, the place to go is probably the mediawiki.org web site. --
534:
922:. This last may force lengthy (ie, time expensive) reads of mass storage before a binary search can be started.
878:
791:
443:
219:
190:
1126:
125:
1159:
998:
994:
1118:
783:
668:
1098:
808:
734:? Do they deserve a merging? Is one of these article titles inappropriate? Should one link to the other?
55:
1187:
986:
859:
763:
then, an algorithm that runs only on a non-existant quantum computer exists only in the realm of theory.
748:
175:
70:
803:
Removed the questionable sections on "SQL search" and "tradeoff search", which are subtopics at best.
1144:
sub-topics-generic programming algorithms: arrays, lists, linked lists, etc. Search algorithms -: -->
1026:
1022:
1006:
923:
731:
764:
362:
1030:
990:
694:
672:
161:
1048:
may be appropriate to locate a particular person with given name 'Alice' and perhaps thereafter a
1112:
1014:
676:
635:
606:
This article was the subject of a Wiki
Education Foundation-supported course assignment, between
1174:
together as
Wikilinks, rather than a well-structured, externally sourced encyclopedic article.
578:
1094:
1072:
963:
915:
804:
777:
141:
51:
488:
1183:
874:
708:
700:
414:
266:
24:
926:
is better than binary search for large sorted lists with 'fairly even' key distributions (
837:
656:
Last week it was working fine and produced the correct results. I have checked with our
1078:
1062:
1040:
1002:
927:
903:
891:
619:
330:
767:
659:
Systems
Administrator and had confirmation that nothing was changed over the weekend.
353:
Requested articles/Applied arts and sciences/Computer science, computing, and
Internet
1199:
1049:
1045:
947:
919:
911:
899:
887:
855:
737:
631:
976:. One such exception is hash tables, which cannot perform such searches efficiently.
989:
are likely the most used searching techniques for structured data. They examine
704:
663:
602:
780:
exist now, and one has been sold commercially. 19:56, 10 September 2011 (UTC)
650:
Can anyone help? For some reason our wiki search does not return any results.
943:
833:
1145:
sub-topics: disk-based searching, in-memory searching Graph algorithms -: -->
1010:
395:
1178:
percentage of the overall lifetime of the subject matter's history itself.
253:
232:
1191:
1163:
1137:
Algorithms discussion - can we make this more exhaustive and hierarchical?
1130:
1102:
841:
812:
751:
740:
712:
684:
639:
653:
Even if I search for the exact wiki page - no results are displayed.
1081:
is a general online search–selection algorithm for random input.
1115:
redirects here, but there is nothing in the article about it.
573:
471:
Find pictures for the biographies of computer scientists (see
184:
15:
1052:
to locate a particular address for a specific Alice Smith.
950:
in the average case, but have terrible worst-case time (O(
852:
articles on individual caetgories or individual methods.
934:)) complexity), but has a worst-case running time of O(
160:
1226:
Knowledge (XXG) level-5 vital articles in Mathematics
597:
Wiki Education Foundation-supported course assignment
265:, a collaborative effort to improve the coverage of
966:
for more discussion of list search data structures.
174:
377:Computer science articles needing expert attention
881:of these algorithms has been intensively studied.
1017:), etc. Other examples of tree-searches include
946:can also be used for list searches. They run in
33:for general discussion of the article's subject.
1251:Knowledge (XXG) former articles for improvement
517:WikiProject Computer science/Unreferenced BLPs
1216:Knowledge (XXG) vital articles in Mathematics
8:
823:relationship between search and optimisation
730:) How much overlap does this page have with
279:Knowledge (XXG):WikiProject Computer science
910:) time. This is significantly better than
434:Computer science articles without infoboxes
372:Computer science articles needing attention
188:
338:Here are some tasks awaiting attention:
312:
227:
1231:Start-Class vital articles in Mathematics
628:Template:Dashboard.wikiedu.org assignment
590:on 24 July 2017 for a period of one week.
1241:Top-importance Computer science articles
873:to it). As this is a common problem in
626:Above undated message substituted from
229:
1211:Knowledge (XXG) level-5 vital articles
1246:WikiProject Computer science articles
1236:Start-Class Computer science articles
1146:sub-topics: Sorting algorithms -: -->
282:Template:WikiProject Computer science
7:
829:soundness and completeness of search
826:local vs global search, local optima
259:This article is within the scope of
218:It is of interest to the following
23:for discussing improvements to the
1221:Start-Class level-5 vital articles
956:self-balancing binary search trees
918:) and generally, that the list be
611:
607:
453:Timeline of computing 2020–present
14:
584:This article was selected as the
479:Computing articles needing images
50:New to Knowledge (XXG)? Welcome!
886:The simplest such algorithm is
662:Thanks in advance for your help
614:. Further details are available
601:
577:
329:
252:
231:
198:
189:
45:Click here to start a new topic.
299:This article has been rated as
1:
1192:16:48, 13 December 2014 (UTC)
1068:Search suggest drop-down list
813:20:56, 10 December 2007 (UTC)
533:Tag all relevant articles in
273:and see a list of open tasks.
42:Put new text under old text.
1169:Calling for expert attention
1164:06:29, 30 October 2013 (UTC)
1131:22:07, 9 February 2011 (UTC)
1013:first and backtracking (ie,
752:13:47, 8 November 2005 (UTC)
640:08:50, 17 January 2022 (UTC)
542:WikiProject Computer science
318:WikiProject Computer science
262:WikiProject Computer science
1103:17:58, 4 January 2010 (UTC)
768:05:20, 10 August 2007 (UTC)
725:This notice also posted to
473:List of computer scientists
1267:
1206:Start-Class vital articles
1019:iterative-deepening search
842:10:42, 15 April 2008 (UTC)
727:Talk: Combinatorial search
713:05:25, 8 August 2016 (UTC)
305:project's importance scale
1085:Princess and monster game
757:
685:10:25, 25 July 2005 (UTC)
535:Category:Computer science
311:
298:
285:Computer science articles
247:
226:
80:Be welcoming to newcomers
879:computational complexity
537:and sub-categories with
741:21:31, 4 May 2004 (UTC)
587:article for improvement
987:Tree search algorithms
847:General reorganization
498:Computer science stubs
75:avoid personal attacks
958:and needs only O(log
860:tree search algorithm
618:. Student editor(s):
212:on Knowledge (XXG)'s
205:level-5 vital article
100:Neutral point of view
1027:bidirectional search
1023:depth-limited search
1007:breadth-first search
924:Interpolation search
732:combinatorial search
719:Combinatorial Search
316:Things you can help
105:No original research
1031:uniform-cost search
920:randomly accessible
818:Some missing points
1113:adversarial search
1108:Missing section(s)
1015:depth-first search
758:Grover's Algorithm
616:on the course page
214:content assessment
86:dispute resolution
47:
1121:comment added by
1073:Secretary problem
964:associative array
916:sorting algorithm
805:Bryan Silverthorn
786:comment added by
778:Quantum computers
688:
671:comment added by
594:
593:
572:
571:
568:
567:
564:
563:
560:
559:
556:
555:
183:
182:
66:Assume good faith
43:
1258:
1133:
1093:All the best, --
1009:) or reaching a
1001:is taken from a
875:computer science
795:
701:Search algorithm
698:
687:
665:
642:
613:
609:
605:
581:
574:
546:
540:
415:Computer science
344:Article requests
333:
326:
325:
313:
287:
286:
283:
280:
277:
276:Computer science
267:Computer science
256:
249:
248:
243:
239:Computer science
235:
228:
211:
202:
201:
194:
193:
185:
179:
178:
164:
95:Article policies
25:Search algorithm
16:
1266:
1265:
1261:
1260:
1259:
1257:
1256:
1255:
1196:
1195:
1171:
1139:
1116:
1110:
849:
820:
801:
781:
775:
760:
738:Derrick Coetzee
721:
692:
666:
648:
625:
608:20 January 2021
599:
552:
549:
544:
538:
526:Project-related
521:
502:
483:
457:
438:
419:
400:
381:
357:
284:
281:
278:
275:
274:
241:
209:
199:
121:
116:
115:
114:
91:
61:
12:
11:
5:
1264:
1262:
1254:
1253:
1248:
1243:
1238:
1233:
1228:
1223:
1218:
1213:
1208:
1198:
1197:
1170:
1167:
1138:
1135:
1109:
1106:
1091:
1090:
1089:
1088:
1087:
1082:
1079:Odds algorithm
1076:
1070:
1065:
1063:Ternary search
1054:
1053:
1041:Greater London
1035:
1034:
1003:data structure
984:
978:
977:
968:
967:
940:
939:
883:
882:
870:
864:
853:
848:
845:
831:
830:
827:
824:
819:
816:
800:
797:
788:108.194.44.134
774:
771:
759:
756:
755:
754:
720:
717:
716:
715:
647:
644:
598:
595:
592:
591:
582:
570:
569:
566:
565:
562:
561:
558:
557:
554:
553:
551:
550:
548:
547:
530:
522:
520:
519:
513:
503:
501:
500:
494:
484:
482:
481:
476:
468:
458:
456:
455:
449:
439:
437:
436:
430:
420:
418:
417:
411:
401:
399:
398:
392:
382:
380:
379:
374:
368:
358:
356:
355:
349:
337:
335:
334:
322:
321:
309:
308:
301:Top-importance
297:
291:
290:
288:
271:the discussion
257:
245:
244:
242:Top‑importance
236:
224:
223:
217:
195:
181:
180:
118:
117:
113:
112:
107:
102:
93:
92:
90:
89:
82:
77:
68:
62:
60:
59:
48:
39:
38:
35:
34:
28:
13:
10:
9:
6:
4:
3:
2:
1263:
1252:
1249:
1247:
1244:
1242:
1239:
1237:
1234:
1232:
1229:
1227:
1224:
1222:
1219:
1217:
1214:
1212:
1209:
1207:
1204:
1203:
1201:
1194:
1193:
1189:
1185:
1179:
1175:
1168:
1166:
1165:
1161:
1157:
1152:
1148:
1136:
1134:
1132:
1128:
1124:
1123:134.71.47.130
1120:
1114:
1107:
1105:
1104:
1100:
1096:
1086:
1083:
1080:
1077:
1074:
1071:
1069:
1066:
1064:
1061:
1060:
1059:
1056:
1055:
1051:
1050:linear search
1047:
1046:binary search
1042:
1037:
1036:
1032:
1028:
1024:
1020:
1016:
1012:
1008:
1004:
1000:
996:
992:
988:
985:
983:
980:
979:
975:
970:
969:
965:
961:
957:
953:
949:
948:constant time
945:
942:
941:
937:
933:
929:
925:
921:
917:
913:
912:linear search
909:
905:
902:; it runs in
901:
900:binary search
897:
893:
889:
888:linear search
885:
884:
880:
876:
871:
869:
866:
865:
863:
861:
857:
856:linear search
846:
844:
843:
839:
835:
828:
825:
822:
821:
817:
815:
814:
810:
806:
798:
796:
793:
789:
785:
779:
772:
770:
769:
766:
753:
750:
749:Headstogether
745:
744:
743:
742:
739:
735:
733:
729:
728:
718:
714:
710:
706:
702:
696:
691:
690:
689:
686:
682:
678:
674:
670:
664:
660:
657:
654:
651:
646:Search broken
645:
643:
641:
637:
633:
629:
623:
621:
617:
604:
596:
589:
588:
583:
580:
576:
575:
543:
536:
532:
531:
529:
527:
523:
518:
515:
514:
512:
510:
509:
504:
499:
496:
495:
493:
491:
490:
485:
480:
477:
474:
470:
469:
467:
465:
464:
459:
454:
451:
450:
448:
446:
445:
440:
435:
432:
431:
429:
427:
426:
421:
416:
413:
412:
410:
408:
407:
402:
397:
394:
393:
391:
389:
388:
383:
378:
375:
373:
370:
369:
367:
365:
364:
359:
354:
351:
350:
348:
346:
345:
340:
339:
336:
332:
328:
327:
324:
323:
319:
315:
314:
310:
306:
302:
296:
293:
292:
289:
272:
268:
264:
263:
258:
255:
251:
250:
246:
240:
237:
234:
230:
225:
221:
215:
207:
206:
196:
192:
187:
186:
177:
173:
170:
167:
163:
159:
155:
152:
149:
146:
143:
140:
137:
134:
131:
127:
124:
123:Find sources:
120:
119:
111:
110:Verifiability
108:
106:
103:
101:
98:
97:
96:
87:
83:
81:
78:
76:
72:
69:
67:
64:
63:
57:
53:
52:Learn to edit
49:
46:
41:
40:
37:
36:
32:
26:
22:
18:
17:
1180:
1176:
1172:
1156:75.133.175.2
1153:
1149:
1147:sub-topics:
1140:
1111:
1095:Jorge Stolfi
1092:
1057:
981:
974:range search
973:
959:
951:
935:
931:
907:
895:
867:
850:
832:
802:
782:— Preceding
776:
761:
736:
724:
722:
667:— Preceding
661:
658:
655:
652:
649:
624:
600:
585:
525:
524:
508:Unreferenced
506:
505:
487:
486:
461:
460:
442:
441:
423:
422:
404:
403:
385:
384:
361:
360:
342:
341:
300:
260:
220:WikiProjects
203:
171:
165:
157:
150:
144:
138:
132:
122:
94:
19:This is the
1184:Leprof 7272
1117:—Preceding
982:Tree search
944:Hash tables
894:(n), where
868:List search
210:Start-class
148:free images
31:not a forum
1200:Categories
930:(log (log
612:2 May 2021
1011:leaf node
765:AngleWyrm
620:Rjrno3300
396:Computing
208:is rated
88:if needed
71:Be polite
21:talk page
1119:unsigned
1058:See also
784:unsigned
695:Lenaquin
681:contribs
673:Lenaquin
669:unsigned
632:PrimeBOT
444:Maintain
387:Copyedit
56:get help
29:This is
27:article.
799:Removed
773:Quantum
425:Infobox
363:Cleanup
303:on the
154:WPÂ refs
142:scholar
1029:, and
877:, the
705:Beland
406:Expand
216:scale.
126:Google
995:nodes
991:trees
906:(log
834:Pgr94
489:Stubs
463:Photo
320:with:
197:This
169:JSTOR
130:books
84:Seek
1188:talk
1160:talk
1127:talk
1099:talk
999:node
858:and
838:talk
809:talk
792:talk
709:talk
677:talk
636:talk
610:and
162:FENS
136:news
73:and
993:of
630:by
295:Top
176:TWL
1202::
1190:)
1162:)
1129:)
1101:)
1025:,
1021:,
938:).
862:.
840:)
811:)
794:)
711:)
683:)
679:•
638:)
622:.
545:}}
539:{{
156:)
54:;
1186:(
1158:(
1125:(
1097:(
1033:.
960:n
952:n
936:n
932:n
928:O
908:n
904:O
896:n
892:O
836:(
807:(
790:(
723:(
707:(
697::
693:@
675:(
634:(
528::
511::
492::
475:)
466::
447::
428::
409::
390::
366::
347::
307:.
222::
172:·
166:·
158:·
151:·
145:·
139:·
133:·
128:(
58:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.