173:, 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
325:
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
165:
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.
496:
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.
81:(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
166:
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.
194:
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":
177:. 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
814:
795:
879:
843:
906:
771:
867:
89:," due to a joke where this is used as a physical sentinel. In safe languages, most sentinel values could be replaced with
756:
170:
59:
799:
109:
901:
746:
123:
82:
130:
31:
766:
875:
839:
810:
751:
86:
832:
78:
133:
in a stream of equally spaced data values, for example, a set 8th bit in a stream of 7-bit
504:
the last element of the array by a sentinel and handle it, especially if it is reached:
871:
105:
895:
791:
741:
142:
20:
859:
761:
736:
115:
67:
24:
156:
A negative integer for indicating the end of a sequence of non-negative integers.
119:
90:
174:
63:
326:
is more realistic for a linked list, as below), this can be rewritten as:
146:
150:
74:
66:
which uses its presence as a condition of termination, typically in a
169:
For instance, when searching for a particular value in an unsorted
134:
77:
data that makes it possible to detect the end of the data when no
16:
In-band data value that must be handled specially by computer code
138:
93:, which enforce explicit handling of the exceptional case.
101:
Some examples of common sentinel values and their uses:
838:(2nd ed.). Redmond: Microsoft Press. p. 621.
800:"3. Representing Sequences by Arrays and Linked Lists"
831:
807:Algorithms and Data Structures: The Basic Toolbox
85:). A sentinel value is sometimes known as an "
8:
783:
7:
141:indicating a special property (like
500:It is also possible to temporarily
14:
772:Time formatting and storage bugs
73:The sentinel value is a form of
868:The Art of Computer Programming
1:
118:for indicating the end of a
108:for indicating the end of a
153:) or the end of the stream.
137:characters stored in 8-bit
925:
757:Magic number (programming)
18:
830:McConnell, Steve (2004).
809:. Springer. p. 63.
506:
328:
197:
181:rather than a sentinel.
70:or recursive algorithm.
19:Not to be confused with
907:Trees (data structures)
38:(also referred to as a
110:null-terminated string
864:Sorting and searching
747:Semipredicate problem
608:// add sentinel value
391:// add sentinel value
83:semipredicate problem
62:in the context of an
131:most significant bit
32:computer programming
767:Null object pattern
816:978-3-540-77977-3
752:Elephant in Cairo
87:Elephant in Cairo
914:
886:
885:
856:
850:
849:
837:
827:
821:
820:
804:
788:
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:
516:
513:
510:
495:
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:
338:
335:
332:
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:
207:
204:
201:
79:out-of-band data
924:
923:
917:
916:
915:
913:
912:
911:
892:
891:
890:
889:
882:
874:. p. 395.
870:. Vol. 3.
858:
857:
853:
846:
829:
828:
824:
817:
802:
790:
789:
785:
780:
733:
728:
727:
724:
721:
718:
715:
712:
709:
706:
703:
700:
697:
694:
691:
688:
685:
682:
679:
676:
673:
670:
667:
664:
661:
658:
655:
652:
649:
646:
643:
640:
637:
634:
631:
628:
625:
622:
619:
616:
613:
610:
607:
604:
601:
598:
595:
592:
589:
586:
583:
580:
577:
574:
571:
568:
565:
562:
559:
556:
553:
550:
547:
544:
541:
538:
535:
532:
529:
526:
523:
520:
517:
514:
511:
508:
493:
490:
489:
486:
483:
480:
477:
474:
471:
468:
465:
462:
459:
456:
453:
450:
447:
444:
441:
438:
435:
432:
429:
426:
423:
420:
417:
414:
411:
408:
405:
402:
399:
396:
393:
390:
387:
384:
381:
378:
375:
372:
369:
366:
363:
360:
357:
354:
351:
348:
345:
342:
339:
336:
333:
330:
323:
322:
319:
316:
313:
310:
307:
304:
301:
298:
295:
292:
289:
286:
283:
280:
277:
274:
271:
268:
265:
262:
259:
256:
253:
250:
247:
244:
241:
238:
235:
232:
229:
226:
223:
220:
217:
214:
211:
208:
205:
202:
199:
192:
187:
163:
99:
58:) is a special
28:
17:
12:
11:
5:
922:
921:
918:
910:
909:
904:
894:
893:
888:
887:
880:
872:Addison-Wesley
851:
844:
822:
815:
796:Sanders, Peter
792:Mehlhorn, Kurt
782:
781:
779:
776:
775:
774:
769:
764:
759:
754:
749:
744:
739:
732:
729:
507:
329:
198:
191:
188:
186:
183:
162:
159:
158:
157:
154:
127:
113:
106:Null character
98:
95:
36:sentinel value
15:
13:
10:
9:
6:
4:
3:
2:
920:
919:
908:
905:
903:
900:
899:
897:
883:
881:0-201-03803-X
877:
873:
869:
865:
861:
860:Knuth, Donald
855:
852:
847:
845:0-7356-1967-0
841:
836:
835:
834:Code Complete
826:
823:
818:
812:
808:
801:
797:
793:
787:
784:
777:
773:
770:
768:
765:
763:
760:
758:
755:
753:
750:
748:
745:
743:
742:Sentinel node
740:
738:
735:
734:
730:
505:
503:
498:
492:The test for
327:
196:
189:
184:
182:
180:
176:
172:
167:
160:
155:
152:
148:
144:
143:inverse video
140:
136:
132:
128:
125:
121:
117:
114:
111:
107:
104:
103:
102:
96:
94:
92:
88:
84:
80:
76:
71:
69:
65:
61:
57:
53:
49:
45:
41:
37:
33:
26:
22:
21:sentinel node
902:Linked lists
863:
854:
833:
825:
806:
786:
762:Magic string
737:Canary value
722:// not found
501:
499:
491:
484:// not found
324:
317:// not found
193:
178:
168:
164:
116:Null pointer
100:
91:option types
72:
55:
52:signal value
51:
47:
43:
39:
35:
29:
25:canary value
179:dummy value
120:linked list
48:rogue value
896:Categories
778:References
494:i < len
175:inner loop
56:dummy data
44:trip value
40:flag value
64:algorithm
862:(1973).
798:(2008).
731:See also
185:Examples
161:Variants
147:boldface
97:Examples
502:replace
151:italics
75:in-band
878:
842:
813:
713:return
701:return
575:return
527:size_t
475:return
463:return
349:size_t
308:return
299:return
218:size_t
129:A set
803:(PDF)
665:break
439:break
190:Array
139:bytes
135:ASCII
122:or a
60:value
54:, or
876:ISBN
840:ISBN
811:ISBN
710:else
677:last
584:last
551:last
512:find
472:else
454:<
334:find
263:<
203:find
171:list
124:tree
68:loop
34:, a
695:val
689:arr
671:arr
659:val
653:arr
620:for
611:int
602:val
596:arr
590:arr
563:len
548:int
539:val
536:int
530:len
521:arr
518:int
509:int
457:len
433:val
427:arr
394:for
385:val
379:arr
370:int
361:val
358:int
352:len
343:arr
340:int
331:int
293:val
287:arr
266:len
245:int
239:for
230:val
227:int
221:len
212:arr
209:int
200:int
149:or
30:In
23:or
898::
866:.
805:.
794:;
716:-1
692:==
683:if
656:==
647:if
641:++
635:;;
578:-1
566:==
557:if
478:-1
445:if
430:==
421:if
415:++
409:;;
311:-1
290:==
281:if
275:++
145:,
50:,
46:,
42:,
884:.
848:.
819:.
725:}
719:;
707:;
704:i
698:)
686:(
680:;
674:=
668:;
662:)
650:(
644:)
638:i
632:0
629:=
626:i
623:(
617:;
614:i
605:;
599:=
593:;
587:=
581:;
572:)
569:0
560:(
554:;
545:{
542:)
533:,
524:,
515:(
487:}
481:;
469:;
466:i
460:)
451:i
448:(
442:;
436:)
424:(
418:)
412:i
406:0
403:=
400:i
397:(
388:;
382:=
376:;
373:i
367:{
364:)
355:,
346:,
337:(
320:}
314:;
305:;
302:i
296:)
284:(
278:)
272:i
269:;
260:i
257:;
254:0
251:=
248:i
242:(
236:{
233:)
224:,
215:,
206:(
126:.
112:.
27:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.