73:
175:
32:
1130:), in practice even on medium-sized arrays (around 100 items or less) it might be infeasible to use anything else. On larger arrays, it only makes sense to use other, faster search methods if the data is large enough, because the initial time to prepare (sort) the data is comparable to many linear searches.
948:
1092:
The performance of linear search improves if the desired value is more likely to be near the beginning of the list than to its end. Therefore, if some values are much more likely to be searched than others, it is desirable to place them at the beginning of the list.
823:
items, the best case is when the value is equal to the first element of the list, in which case only one comparison is needed. The worst case is when the value is not in the list (or occurs only once at the end of the list), in which case
647:) that equals the target, the second comparison can be eliminated until the end of the search, making the algorithm faster. The search will reach the sentinel if the target is not contained within the list.
841:
1060:
986:
1108:
Linear search is usually very simple to implement, and is practical when the list has only a few elements, or when performing a single search in an un-ordered list.
953:
For example, if the value being sought occurs once in the list, and all orderings of the list are equally likely, the expected number of comparisons is
185:
447:
comparisons, but the average case can be affected if the search probabilities for each element vary. Linear search is rarely practical because other
1111:
When many values have to be searched in the same list, it often pays to pre-process the list in order to use a faster method. For example, one may
1311:
1274:
269:
156:
59:
943:{\displaystyle {\begin{cases}n&{\mbox{if }}k=0\\\displaystyle {\frac {n+1}{k+1}}&{\mbox{if }}1\leq k\leq n.\end{cases}}}
1302:
467:
A linear search sequentially checks each element of the list until it finds an element that matches the target value. If the
200:
94:
90:
45:
1002:
243:
137:
1123:
from it. Should the content of the list change frequently, repeated re-organization may be more trouble than it is worth.
215:
109:
412:
360:
338:
320:
298:
427:
is the length of the list. If each element is equally likely to be searched, then linear search has an average case of
222:
116:
1326:
83:
492:
1096:
In particular, when the list items are arranged in order of decreasing probability, and these probabilities are
229:
123:
1217:
404:. It sequentially checks each element of the list until a match is found or the whole list has been searched.
1116:
452:
850:
835:
times in the list, and all orderings of the list are equally likely, the expected number of comparisons is
1126:
As a result, even though in theory other search algorithms may be faster than linear search (for instance
1097:
211:
105:
1149:
1120:
1073:
956:
1269:. The Art of Computer Programming. Vol. 3 (3rd ed.). Addison-Wesley. pp. 396–408.
51:
738:, the search can establish the absence of the target more quickly by concluding the search once
1307:
1270:
1112:
448:
401:
389:
363:
291:
236:
130:
408:
341:
323:
301:
749:
exceeds the target. This variation requires a sentinel that is greater than the target.
1172:
1170:
1139:
1077:
644:
368:
346:
328:
306:
1320:
1127:
1294:
1262:
174:
72:
17:
611:
The basic algorithm above makes two comparisons per iteration: one to check if
1144:
520:
456:
468:
1218:"Binary search and linear search performance on the .NET and Mono platform"
1305:. Vol. 3 (2nd ed.). Reading, MA: Addison-Wesley Professional.
996:- 1 comparisons are needed, and the expected number of comparisons is
632:
still points to a valid index of the list. By adding an extra record
1076:
the worst-case cost and the expected cost of linear search are both
192:
471:
reaches the end of the list, the search terminates unsuccessfully.
1069:= 2 this is 1, corresponding to a single if-then-else construct).
591:, go to step 2. Otherwise, the search terminates unsuccessfully.
459:, allow significantly faster searching for all but short lists.
168:
66:
25:
936:
1252:, §6.1 ("Sequential search"), subsection "Algorithm T".
1240:, §6.1 ("Sequential search"), subsection "Algorithm Q".
1203:, §6.1 ("Sequential search"), subsection "Algorithm B".
196:
1055:{\displaystyle \displaystyle {\frac {(n+2)(n-1)}{2n}}}
909:
859:
1006:
1005:
959:
878:
844:
523:uses linear search to find the index of the target
378:
359:
337:
319:
297:
287:
97:. Unsourced material may be challenged and removed.
1054:
980:
942:
1265:(1997). "Section 6.1: Sequential Searching".
810:. Else, the search terminates unsuccessfully.
804:, the search terminates successfully; return
703:. Else, the search terminates unsuccessfully.
697:, the search terminates successfully; return
563:, the search terminates successfully; return
8:
400:is a method for finding an element within a
282:
201:introducing citations to additional sources
1191:, §6.2 ("Searching by Comparison Of Keys").
1100:, the cost of linear search is only O(1).
60:Learn how and when to remove these messages
1007:
1004:
960:
958:
908:
879:
858:
845:
843:
270:Learn how and when to remove this message
157:Learn how and when to remove this message
191:Relevant discussion may be found on the
1166:
281:
1249:
1237:
1200:
1188:
1176:
7:
1211:
1209:
95:adding citations to reliable sources
992:that it occurs once, then at most
14:
831:If the value being sought occurs
712:If the list is ordered such that
41:This article has multiple issues.
981:{\displaystyle {\frac {n+1}{2}}}
184:relies largely or entirely on a
173:
71:
30:
23:Sequentially looking in an array
1303:The Art of Computer Programming
82:needs additional citations for
49:or discuss these issues on the
1037:
1025:
1022:
1010:
1:
1179:, §6.1 ("Sequential search").
626:, and the other to check if
1345:
15:
1098:geometrically distributed
1088:Non-uniform probabilities
451:and schemes, such as the
1119:, or build an efficient
828:comparisons are needed.
491:elements with values or
407:A linear search runs in
16:Not to be confused with
453:binary search algorithm
1056:
982:
944:
786:by 1 and go to step 2.
684:by 1 and go to step 2.
1299:Sorting and Searching
1267:Sorting and Searching
1150:Linear search problem
1121:search data structure
1057:
983:
945:
1003:
988:. However, if it is
957:
842:
415:, and makes at most
197:improve this article
91:improve this article
708:In an ordered table
513:, and target value
421:comparisons, where
284:
1065:(for example, for
1052:
1051:
978:
940:
935:
913:
905:
863:
1327:Search algorithms
1115:the list and use
1049:
976:
912:
903:
862:
449:search algorithms
398:sequential search
386:
385:
280:
279:
272:
262:
261:
247:
167:
166:
159:
141:
64:
1334:
1306:
1281:
1280:
1259:
1253:
1247:
1241:
1235:
1229:
1228:
1226:
1224:
1213:
1204:
1198:
1192:
1186:
1180:
1174:
1061:
1059:
1058:
1053:
1050:
1048:
1040:
1008:
987:
985:
984:
979:
977:
972:
961:
949:
947:
946:
941:
939:
938:
914:
910:
904:
902:
891:
880:
864:
860:
819:For a list with
809:
803:
785:
776:
758:
748:
737:
702:
696:
683:
674:
656:
642:
631:
621:
608:
607:
603:
590:
577:
568:
562:
544:
534:
528:
519:, the following
518:
512:
490:
484:
446:
445:
443:
442:
439:
436:
426:
420:
390:computer science
364:space complexity
292:Search algorithm
285:
275:
268:
257:
254:
248:
246:
205:
177:
169:
162:
155:
151:
148:
142:
140:
99:
75:
67:
56:
34:
33:
26:
1344:
1343:
1337:
1336:
1335:
1333:
1332:
1331:
1317:
1316:
1293:
1290:
1285:
1284:
1277:
1261:
1260:
1256:
1248:
1244:
1236:
1232:
1222:
1220:
1216:Horvath, Adam.
1215:
1214:
1207:
1199:
1195:
1187:
1183:
1175:
1168:
1163:
1158:
1136:
1106:
1090:
1041:
1009:
1001:
1000:
962:
955:
954:
934:
933:
906:
892:
881:
875:
874:
856:
846:
840:
839:
817:
805:
798:
790:
781:
777:, go to step 4.
771:
763:
754:
747:
739:
736:
726:
719:
713:
710:
698:
688:
679:
675:, go to step 4.
669:
661:
652:
643:to the list (a
641:
633:
627:
620:
612:
609:
605:
601:
599:
598:
596:With a sentinel
582:
573:
564:
557:
549:
540:
530:
524:
514:
511:
501:
495:
486:
480:
477:
475:Basic algorithm
465:
440:
437:
432:
431:
429:
428:
422:
416:
276:
265:
264:
263:
258:
252:
249:
212:"Linear search"
206:
204:
190:
178:
163:
152:
146:
143:
106:"Linear search"
100:
98:
88:
76:
35:
31:
24:
21:
12:
11:
5:
1342:
1341:
1338:
1330:
1329:
1319:
1318:
1315:
1314:
1289:
1286:
1283:
1282:
1275:
1254:
1242:
1230:
1205:
1193:
1181:
1165:
1164:
1162:
1159:
1157:
1154:
1153:
1152:
1147:
1142:
1140:Ternary search
1135:
1132:
1105:
1102:
1089:
1086:
1074:asymptotically
1063:
1062:
1047:
1044:
1039:
1036:
1033:
1030:
1027:
1024:
1021:
1018:
1015:
1012:
975:
971:
968:
965:
951:
950:
937:
932:
929:
926:
923:
920:
917:
907:
901:
898:
895:
890:
887:
884:
877:
876:
873:
870:
867:
857:
855:
852:
851:
849:
816:
813:
812:
811:
794:
787:
778:
767:
760:
743:
731:
724:
717:
709:
706:
705:
704:
685:
676:
665:
658:
645:sentinel value
637:
616:
597:
594:
593:
592:
579:
570:
553:
546:
506:
499:
476:
473:
464:
461:
384:
383:
380:
376:
375:
366:
357:
356:
344:
335:
334:
326:
317:
316:
304:
295:
294:
289:
278:
277:
260:
259:
195:. Please help
181:
179:
172:
165:
164:
79:
77:
70:
65:
39:
38:
36:
29:
22:
13:
10:
9:
6:
4:
3:
2:
1340:
1339:
1328:
1325:
1324:
1322:
1313:
1312:0-201-89685-0
1309:
1304:
1300:
1296:
1295:Knuth, Donald
1292:
1291:
1287:
1278:
1276:0-201-89685-0
1272:
1268:
1264:
1263:Knuth, Donald
1258:
1255:
1251:
1246:
1243:
1239:
1234:
1231:
1219:
1212:
1210:
1206:
1202:
1197:
1194:
1190:
1185:
1182:
1178:
1173:
1171:
1167:
1160:
1155:
1151:
1148:
1146:
1143:
1141:
1138:
1137:
1133:
1131:
1129:
1128:binary search
1124:
1122:
1118:
1117:binary search
1114:
1109:
1103:
1101:
1099:
1094:
1087:
1085:
1083:
1079:
1075:
1070:
1068:
1045:
1042:
1034:
1031:
1028:
1019:
1016:
1013:
999:
998:
997:
995:
991:
973:
969:
966:
963:
930:
927:
924:
921:
918:
915:
899:
896:
893:
888:
885:
882:
871:
868:
865:
853:
847:
838:
837:
836:
834:
829:
827:
822:
814:
808:
802:
797:
793:
788:
784:
779:
775:
770:
766:
761:
757:
752:
751:
750:
746:
742:
734:
730:
723:
716:
707:
701:
695:
691:
686:
682:
677:
673:
668:
664:
659:
655:
650:
649:
648:
646:
640:
636:
630:
625:
619:
615:
604:
595:
589:
585:
580:
576:
571:
567:
561:
556:
552:
547:
543:
538:
537:
536:
533:
527:
522:
517:
509:
505:
498:
494:
489:
483:
479:Given a list
474:
472:
470:
462:
460:
458:
454:
450:
435:
425:
419:
414:
410:
405:
403:
399:
395:
394:linear search
391:
381:
377:
373:
371:
367:
365:
362:
358:
355:
353:
349:
345:
343:
340:
336:
333:
331:
327:
325:
322:
318:
315:
313:
309:
305:
303:
300:
296:
293:
290:
286:
283:Linear search
274:
271:
256:
253:November 2010
245:
242:
238:
235:
231:
228:
224:
221:
217:
214: –
213:
209:
208:Find sources:
202:
198:
194:
188:
187:
186:single source
182:This article
180:
176:
171:
170:
161:
158:
150:
147:November 2010
139:
136:
132:
129:
125:
122:
118:
115:
111:
108: –
107:
103:
102:Find sources:
96:
92:
86:
85:
80:This article
78:
74:
69:
68:
63:
61:
54:
53:
48:
47:
42:
37:
28:
27:
19:
1298:
1266:
1257:
1245:
1233:
1221:. Retrieved
1196:
1184:
1125:
1110:
1107:
1095:
1091:
1081:
1072:Either way,
1071:
1066:
1064:
993:
989:
952:
832:
830:
825:
820:
818:
806:
800:
795:
791:
782:
773:
768:
764:
755:
744:
740:
732:
728:
727:... ≤
721:
714:
711:
699:
693:
689:
680:
671:
666:
662:
653:
638:
634:
628:
623:
617:
613:
610:
587:
583:
574:
565:
559:
554:
550:
541:
531:
525:
515:
507:
503:
496:
487:
481:
478:
466:
433:
423:
417:
406:
397:
393:
387:
369:
351:
347:
329:
311:
307:
266:
250:
240:
233:
226:
219:
207:
183:
153:
144:
134:
127:
120:
113:
101:
89:Please help
84:verification
81:
57:
50:
44:
43:Please help
40:
1104:Application
457:hash tables
409:linear time
342:performance
324:performance
302:performance
18:Line search
1250:Knuth 1998
1238:Knuth 1998
1201:Knuth 1998
1189:Knuth 1998
1177:Knuth 1998
1156:References
1145:Hash table
521:subroutine
413:worst case
361:Worst-case
299:Worst-case
223:newspapers
117:newspapers
46:improve it
1161:Citations
1032:−
925:≤
919:≤
780:Increase
678:Increase
572:Increase
469:algorithm
463:Algorithm
374:iterative
321:Best-case
193:talk page
52:talk page
1321:Category
1297:(1998).
1223:19 April
1134:See also
911:if
861:if
815:Analysis
772:≥
720:≤
622:equals
493:records
444:
430:
411:in the
379:Optimal
339:Average
237:scholar
131:scholar
1310:
1273:
600:": -->
239:
232:
225:
218:
210:
133:
126:
119:
112:
104:
1288:Works
990:known
759:to 0.
692:<
657:to 0.
586:<
578:by 1.
545:to 0.
502:....
288:Class
244:JSTOR
230:books
138:JSTOR
124:books
1308:ISBN
1271:ISBN
1225:2013
1113:sort
753:Set
651:Set
602:edit
539:Set
455:and
402:list
216:news
110:news
1084:).
789:If
762:If
687:If
660:If
581:If
548:If
529:in
485:of
434:n+1
396:or
388:In
382:Yes
372:(1)
332:(1)
199:by
93:by
1323::
1301:.
1208:^
1169:^
799:=
735:−1
670:=
558:=
535:.
510:−1
392:,
55:.
1279:.
1227:.
1082:n
1080:(
1078:O
1067:n
1046:n
1043:2
1038:)
1035:1
1029:n
1026:(
1023:)
1020:2
1017:+
1014:n
1011:(
994:n
974:2
970:1
967:+
964:n
931:.
928:n
922:k
916:1
900:1
897:+
894:k
889:1
886:+
883:n
872:0
869:=
866:k
854:n
848:{
833:k
826:n
821:n
807:i
801:T
796:i
792:L
783:i
774:T
769:i
765:L
756:i
745:i
741:L
733:n
729:L
725:1
722:L
718:0
715:L
700:i
694:n
690:i
681:i
672:T
667:i
663:L
654:i
639:n
635:L
629:i
624:T
618:i
614:L
606:]
588:n
584:i
575:i
569:.
566:i
560:T
555:i
551:L
542:i
532:L
526:T
516:T
508:n
504:L
500:0
497:L
488:n
482:L
441:2
438:/
424:n
418:n
370:O
354:)
352:n
350:(
348:O
330:O
314:)
312:n
310:(
308:O
273:)
267:(
255:)
251:(
241:·
234:·
227:·
220:·
203:.
189:.
160:)
154:(
149:)
145:(
135:·
128:·
121:·
114:·
87:.
62:)
58:(
20:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
