Why does a sentinel linear search drop the bounds check, and what does that cost?
answer
- count the tests done per iteration
- what guarantees the loop stops
- the buffer needs a spare slot
- stopping at the live count means a miss
- a predicted branch was already nearly free
basics
~20 sWriting the target into a spare slot just past the last live record guarantees the loop terminates on a match, so each iteration tests equality only, never the end of the buffer. It costs a writable spare slot, a restore, and a check that the hit was not the sentinel.
solid answer
~50 sA plain scan performs two tests per iteration: *have I run off the end* and *does this element match*. Placing a copy of the target in the slot immediately after the live data makes the first test redundant — the loop cannot run off the end, because it is guaranteed to match at the sentinel at the latest. That halves the per-iteration comparisons in a naive translation. The costs are real: the buffer needs a spare writable slot, the search **mutates** shared data and must restore it, and the loop's exit needs an extra check afterwards — stopping at an index equal to the live element count means only the sentinel matched, which is a miss, not a hit. Getting that boundary wrong reports a phantom result. And on modern hardware the win is often near zero: the bounds branch is taken identically on almost every iteration, so the predictor already hides it. Measure before adopting.
code
pseudocode · 10 linesn = live_count // buffer has a spare slot at index n
saved = a[n]
a[n] = target // sentinel guarantees the loop stops
i = 0
while a[i] != target // no i < n test in the loop
i = i + 1
a[n] = saved // must restore, on every path
if i == n
return NOT_FOUND // only the sentinel matched
return igo deeper
Know that the trick plants a guaranteed match past the last element so the loop cannot run off the end, and that the cost stays linear. It removes a check, not work proportional to n.
Explain both halves precisely: which comparison disappears, why a stopping index equal to the live count means not found, and why the buffer needs a spare writable slot and a restore.
Judge it, do not just describe it. Note that the removed branch is almost perfectly predicted, that the search now mutates shared state, and that the decision belongs to a benchmark rather than to tradition.
Frame when micro-optimizations like this are allowed at all: a measured hot path, an owned buffer, and a test for the miss boundary — otherwise the simpler loop wins on the cost of every future reader.
## The trick In a straightforward sequential scan, every iteration does two things: it checks whether the position is still within the collection, and it checks whether the current element matches the target. The sentinel variant removes the first check by making it impossible to fail — write a copy of the target into the slot immediately after the last live element, and the loop is guaranteed to stop, because in the worst case it stops on the copy you just planted. After the loop, one comparison distinguishes the two ways it could have ended: if the stopping index equals the live element count, the only thing that matched was the sentinel, so the target is absent. Any smaller index is a genuine hit. ## What it actually buys In a naive translation, per-iteration work drops from two comparisons and two branches to one of each. On a hot scan over a buffer of records, that is a real and measurable reduction in instructions retired — which is why the technique was standard advice for decades. The modern caveat is that instructions retired is not latency. The bounds branch in a scan is one of the most predictable branches a processor will ever see: it goes the same way on every iteration but the last. A branch predictor gets it right essentially always, so the branch costs close to nothing to begin with, and removing something that costs nothing saves nothing. On top of that, compilers frequently hoist or eliminate redundant bounds checks on their own when they can prove the range. The realistic outcome today ranges from a small win on very hot loops to no measurable difference at all — and occasionally a loss, once you count the write and the restore. It is worth noting that runtimes differ substantially in what they charge for the check being removed: memory-safe environments such as those behind Java, Go and C# insert a bounds check on indexed access and lean on the compiler to elide it where the range is provable, while C and C++ insert none at all. The same source-level trick therefore removes different amounts of work depending on where it runs — which is itself the reason to measure rather than to assume. ## What it costs **A writable spare slot.** The buffer must have capacity for one element beyond its live contents. If it does not, the sentinel write is an overflow — the exact class of bug the bounds check existed to prevent. Trading a check for an unchecked write is only safe when the extra capacity is guaranteed by construction. **Mutation of the data being searched.** This is the cost people forget. A search that writes is no longer a read-only operation. Two concurrent scans over the same buffer will overwrite each other's sentinels and can return wrong answers; a scan over a shared or immutable buffer cannot use the technique at all. Restoring the saved value afterwards is mandatory, and any early return that skips the restore corrupts the buffer permanently. **A boundary condition to get right.** The stopping index equal to the live count means *not found*. Treating it as a hit returns the sentinel — a phantom record that looks exactly like the thing you searched for, because it is a copy of it. This is a genuinely nasty bug: it produces plausible data rather than a crash. **Reviewability.** The plain scan is obvious to every reader. The sentinel version needs a comment explaining the spare slot, the restore and the post-loop check, and it needs a test for the miss case specifically. ## When it is still justified A measured hot loop, a buffer you exclusively own with guaranteed spare capacity, an environment where the removed check is genuinely charged, and a benchmark showing a difference you care about. If any of those four is missing, write the plain scan. The broader lesson generalizes past this one trick: an optimization that provably removes work is not automatically an optimization that removes *time*, and one that converts a read into a write has changed the operation's contract — concurrency, immutability and exception safety are all affected. Both of those are worth stating out loud, because the interviewer is usually probing for whether you evaluate micro-optimizations by measurement or by folklore.
- What breaks if two workers scan the same buffer with the sentinel trick at once?The technique writes into the shared buffer, so concurrent scans overwrite each other's sentinels. One worker can stop early on another's target and report a hit that never existed, or find its own sentinel restored mid-scan and run past the end. It is only safe on a buffer the scan exclusively owns, or on a per-worker copy.
- How would you decide whether the sentinel version is actually worth keeping?Benchmark it against the plain scan at your real sizes and hit rates, counting the write and the restore, and include the miss case since that is the full-length path. Then weigh any measured gain against a loop that every reviewer must be told how to read. Absent a difference you can defend, keep the simple version.
Putting a copy of the book you are looking for at the end of the shelf, so you can stop when you find it without also checking whether you have run out of shelf.
saying these in an interview costs you the question
- Thinks the sentinel improves the asymptotic bound
- Forgets to restore the overwritten slot
- Treats a stop at the live count as a hit
- Assumes the trick is safe on shared or read-only data
- Claims fewer comparisons always means less time