184:, every element will be compared against this value, with the loop terminating when equality is found; however, to deal with the case that the value should be absent, one must also test after each step for having completed the search unsuccessfully. By appending the value searched for to the end of the list, an unsuccessful search is no longer possible, and no explicit termination test is required in the
336:
However, this does two tests at each iteration of the loop: whether the value has been found and whether the end of the array has been reached. This latter test is what is avoided by using a sentinel value. Assuming the array can be extended by one element (without memory allocation or cleanup; this
176:
A related practice, used in slightly different circumstances, is to place some specific value at the end of the data, in order to avoid the need for an explicit test for termination in some processing loop, because the value will trigger termination by the tests already present for other reasons.
507:
is still present, but it has been moved outside the loop, which now contains only a single test (for the value), and is guaranteed to terminate due to the sentinel value. There is a single check on termination if the sentinel value has been hit, which replaces a test for each iteration.
92:(such as an explicit size indication) is provided. The value should be selected in such a way that it is guaranteed to be distinct from all legal data values since otherwise, the presence of such values would prematurely signal the end of the data (the
177:
Unlike the above uses, this is not how the data is naturally stored or processed, but is instead an optimization, compared to the straightforward algorithm that checks for termination. This is typically used in searching.
205:
For example, if searching for a value in an array in C, a straightforward implementation is as follows; note the use of a negative number (invalid index) to solve the semipredicate problem of returning "no result":
188:. After the search, one must decide whether a true match was found, but this test needs to be performed only once rather than at each iteration. Knuth calls the value so placed at the end of the data, a
825:
806:
890:
854:
917:
782:
878:
100:," due to a joke where this is used as a physical sentinel. In safe languages, most sentinel values could be replaced with
767:
181:
70:
810:
120:
912:
757:
134:
93:
141:
42:
777:
886:
850:
821:
762:
97:
843:
89:
144:
in a stream of equally spaced data values, for example, a set 8th bit in a stream of 7-bit
515:
the last element of the array by a sentinel and handle it, especially if it is reached:
882:
116:
906:
802:
752:
153:
31:
870:
772:
747:
126:
78:
35:
167:
A negative integer for indicating the end of a sequence of non-negative integers.
130:
101:
185:
74:
17:
337:
is more realistic for a linked list, as below), this can be rewritten as:
157:
161:
85:
77:
which uses its presence as a condition of termination, typically in a
180:
For instance, when searching for a particular value in an unsorted
145:
88:
data that makes it possible to detect the end of the data when no
27:
In-band data value that must be handled specially by computer code
149:
104:, which enforce explicit handling of the exceptional case.
112:
Some examples of common sentinel values and their uses:
849:(2nd ed.). Redmond: Microsoft Press. p. 621.
811:"3. Representing Sequences by Arrays and Linked Lists"
842:
818:Algorithms and Data Structures: The Basic Toolbox
96:). A sentinel value is sometimes known as an "
8:
794:
7:
152:indicating a special property (like
511:It is also possible to temporarily
25:
783:Time formatting and storage bugs
84:The sentinel value is a form of
879:The Art of Computer Programming
1:
129:for indicating the end of a
119:for indicating the end of a
164:) or the end of the stream.
148:characters stored in 8-bit
934:
768:Magic number (programming)
29:
841:McConnell, Steve (2004).
820:. Springer. p. 63.
517:
339:
208:
192:rather than a sentinel.
81:or recursive algorithm.
30:Not to be confused with
918:Trees (data structures)
49:(also referred to as a
121:null-terminated string
875:Sorting and searching
758:Semipredicate problem
619:// add sentinel value
402:// add sentinel value
94:semipredicate problem
73:in the context of an
142:most significant bit
43:computer programming
778:Null object pattern
827:978-3-540-77977-3
763:Elephant in Cairo
98:Elephant in Cairo
16:(Redirected from
925:
897:
896:
867:
861:
860:
848:
838:
832:
831:
815:
799:
737:
734:
731:
728:
725:
722:
719:
716:
713:
710:
707:
704:
701:
698:
695:
692:
689:
686:
683:
680:
677:
674:
671:
668:
665:
662:
659:
656:
653:
650:
647:
644:
641:
638:
635:
632:
629:
626:
623:
620:
617:
614:
611:
608:
605:
602:
599:
596:
593:
590:
587:
584:
581:
578:
575:
572:
569:
566:
563:
560:
557:
554:
551:
548:
545:
542:
539:
536:
533:
530:
527:
524:
521:
506:
499:
496:
493:
490:
487:
484:
481:
478:
475:
472:
469:
466:
463:
460:
457:
454:
451:
448:
445:
442:
439:
436:
433:
430:
427:
424:
421:
418:
415:
412:
409:
406:
403:
400:
397:
394:
391:
388:
385:
382:
379:
376:
373:
370:
367:
364:
361:
358:
355:
352:
349:
346:
343:
332:
329:
326:
323:
320:
317:
314:
311:
308:
305:
302:
299:
296:
293:
290:
287:
284:
281:
278:
275:
272:
269:
266:
263:
260:
257:
254:
251:
248:
245:
242:
239:
236:
233:
230:
227:
224:
221:
218:
215:
212:
90:out-of-band data
21:
933:
932:
928:
927:
926:
924:
923:
922:
903:
902:
901:
900:
893:
885:. p. 395.
881:. Vol. 3.
869:
868:
864:
857:
840:
839:
835:
828:
813:
801:
800:
796:
791:
744:
739:
738:
735:
732:
729:
726:
723:
720:
717:
714:
711:
708:
705:
702:
699:
696:
693:
690:
687:
684:
681:
678:
675:
672:
669:
666:
663:
660:
657:
654:
651:
648:
645:
642:
639:
636:
633:
630:
627:
624:
621:
618:
615:
612:
609:
606:
603:
600:
597:
594:
591:
588:
585:
582:
579:
576:
573:
570:
567:
564:
561:
558:
555:
552:
549:
546:
543:
540:
537:
534:
531:
528:
525:
522:
519:
504:
501:
500:
497:
494:
491:
488:
485:
482:
479:
476:
473:
470:
467:
464:
461:
458:
455:
452:
449:
446:
443:
440:
437:
434:
431:
428:
425:
422:
419:
416:
413:
410:
407:
404:
401:
398:
395:
392:
389:
386:
383:
380:
377:
374:
371:
368:
365:
362:
359:
356:
353:
350:
347:
344:
341:
334:
333:
330:
327:
324:
321:
318:
315:
312:
309:
306:
303:
300:
297:
294:
291:
288:
285:
282:
279:
276:
273:
270:
267:
264:
261:
258:
255:
252:
249:
246:
243:
240:
237:
234:
231:
228:
225:
222:
219:
216:
213:
210:
203:
198:
174:
110:
69:) is a special
39:
28:
23:
22:
15:
12:
11:
5:
931:
929:
921:
920:
915:
905:
904:
899:
898:
891:
883:Addison-Wesley
862:
855:
833:
826:
807:Sanders, Peter
803:Mehlhorn, Kurt
793:
792:
790:
787:
786:
785:
780:
775:
770:
765:
760:
755:
750:
743:
740:
518:
340:
209:
202:
199:
197:
194:
173:
170:
169:
168:
165:
138:
124:
117:Null character
109:
106:
47:sentinel value
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
930:
919:
916:
914:
911:
910:
908:
894:
892:0-201-03803-X
888:
884:
880:
876:
872:
871:Knuth, Donald
866:
863:
858:
856:0-7356-1967-0
852:
847:
846:
845:Code Complete
837:
834:
829:
823:
819:
812:
808:
804:
798:
795:
788:
784:
781:
779:
776:
774:
771:
769:
766:
764:
761:
759:
756:
754:
753:Sentinel node
751:
749:
746:
745:
741:
516:
514:
509:
503:The test for
338:
207:
200:
195:
193:
191:
187:
183:
178:
171:
166:
163:
159:
155:
154:inverse video
151:
147:
143:
139:
136:
132:
128:
125:
122:
118:
115:
114:
113:
107:
105:
103:
99:
95:
91:
87:
82:
80:
76:
72:
68:
64:
60:
56:
52:
48:
44:
37:
33:
32:sentinel node
19:
913:Linked lists
874:
865:
844:
836:
817:
797:
773:Magic string
748:Canary value
733:// not found
512:
510:
502:
495:// not found
335:
328:// not found
204:
189:
179:
175:
127:Null pointer
111:
102:option types
83:
66:
63:signal value
62:
58:
54:
50:
46:
40:
36:canary value
190:dummy value
131:linked list
59:rogue value
18:Rogue value
907:Categories
789:References
505:i < len
186:inner loop
67:dummy data
55:trip value
51:flag value
75:algorithm
873:(1973).
809:(2008).
742:See also
196:Examples
172:Variants
158:boldface
108:Examples
513:replace
162:italics
86:in-band
889:
853:
824:
724:return
712:return
586:return
538:size_t
486:return
474:return
360:size_t
319:return
310:return
229:size_t
140:A set
814:(PDF)
676:break
450:break
201:Array
150:bytes
146:ASCII
133:or a
71:value
65:, or
887:ISBN
851:ISBN
822:ISBN
721:else
688:last
595:last
562:last
523:find
483:else
465:<
345:find
274:<
214:find
182:list
135:tree
79:loop
45:, a
706:val
700:arr
682:arr
670:val
664:arr
631:for
622:int
613:val
607:arr
601:arr
574:len
559:int
550:val
547:int
541:len
532:arr
529:int
520:int
468:len
444:val
438:arr
405:for
396:val
390:arr
381:int
372:val
369:int
363:len
354:arr
351:int
342:int
304:val
298:arr
277:len
256:int
250:for
241:val
238:int
232:len
223:arr
220:int
211:int
160:or
41:In
34:or
909::
877:.
816:.
805:;
727:-1
703:==
694:if
667:==
658:if
652:++
646:;;
589:-1
577:==
568:if
489:-1
456:if
441:==
432:if
426:++
420:;;
322:-1
301:==
292:if
286:++
156:,
61:,
57:,
53:,
895:.
859:.
830:.
736:}
730:;
718:;
715:i
709:)
697:(
691:;
685:=
679:;
673:)
661:(
655:)
649:i
643:0
640:=
637:i
634:(
628:;
625:i
616:;
610:=
604:;
598:=
592:;
583:)
580:0
571:(
565:;
556:{
553:)
544:,
535:,
526:(
498:}
492:;
480:;
477:i
471:)
462:i
459:(
453:;
447:)
435:(
429:)
423:i
417:0
414:=
411:i
408:(
399:;
393:=
387:;
384:i
378:{
375:)
366:,
357:,
348:(
331:}
325:;
316:;
313:i
307:)
295:(
289:)
283:i
280:;
271:i
268:;
265:0
262:=
259:i
253:(
247:{
244:)
235:,
226:,
217:(
137:.
123:.
38:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.