Skip to main content

Sentinel in sequential search

Short answer

A sentinel copy stored at a[n] removes the bound check from the loop, reducing comparisons from two to one per step. This nearly halves work and guarantees termination; if i==n after loop, key not found.

What is the importance of using Sentinel during sequential searching?

A sentinel is a copy of the search key placed just after the last element of the array (a[n] = key). It guarantees that the loop will find the key, so the test "i < n" can be removed from the loop condition.

Importance:

  • The loop makes one comparison per step (a[i] != key) instead of two (i < n and a[i] != key), which almost halves the work for large arrays.
  • The loop always stops, so there is no risk of running past the array end.
  • After the loop, if i == n the key was found only at the sentinel, so it is not in the list.

The array needs one spare location.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Data Structure and Algorithm chapter 8 questions →