Sentinel Search
Places the target at the end of the array as a sentinel, so the scan can skip its bounds check and stop only on a match.
How it works
Sentinel search is a linear search with one trick. A normal linear search does two comparisons per value: "is this the target?" and "have I reached the end?" Sentinel search removes the second one.
It saves the last value, then overwrites the last slot with the target itself: the sentinel. Now the scan is guaranteed to find the target somewhere, so the loop only has to compare each value with the target, and it never needs to check the index. Once it stops, it puts the last value back and looks at where it stopped:
- Before the last slot: a real match, so it returns that index.
- At the last slot: it only hit the sentinel. The target is there only if the saved last value was the target; otherwise it returns -1.
When to use it
The saving is one comparison per value, so it matters in tight loops over large arrays, especially in low-level code. It needs an array it is allowed to write to, and it isn't safe if another thread reads the array during the search. In everyday JavaScript or Python, a plain linear search is just as fast and simpler.
Complexity
| Case | Time | When |
|---|---|---|
| Best | O(1) | The target is the first value |
| Average | O(n) | The target is somewhere in the middle |
| Worst | O(n) | The target is the last value, or isn't there at all |
It does the same number of steps as linear search, but about half the comparisons.
| Extra space | Why |
|---|---|
| O(1) | It only keeps the saved last value and the current index |
Implementations
function sentinelSearch(array, target) {
const n = array.length;
if (n === 0) return -1;
const last = array[n - 1];
array[n - 1] = target;
let i = 0;
while (array[i] !== target) {
i++;
}
array[n - 1] = last;
if (i < n - 1 || last === target) {
return i;
}
return -1;
}
def sentinel_search(array, target):
n = len(array)
if n == 0:
return -1
last = array[n - 1]
array[n - 1] = target
i = 0
while array[i] != target:
i += 1
array[n - 1] = last
if i < n - 1 or last == target:
return i
return -1
#include <vector>
int sentinelSearch(std::vector<int>& a, int target) {
const int n = static_cast<int>(a.size());
if (n == 0) return -1;
int last = a[n - 1];
a[n - 1] = target;
int i = 0;
while (a[i] != target) {
i++;
}
a[n - 1] = last;
if (i < n - 1 || last == target) {
return i;
}
return -1;
}