Linear & Sentinel Search

Linear search is the most basic way to find something in a list: look at each element in turn until you hit a match (or run out). It needs no sorting, no extra structure — just a single left-to-right pass. The sentinel variant is a small optimization that removes one comparison per step by planting the target in an extra slot at the end.

Every iteration of a plain linear search actually does two checks: "am I still inside the array?" (the loop bound) and "is this the value I want?". The sentinel trick collapses that to just one. By copying the key into an extra cell at the very end, you guarantee the search always finds a match, so the loop can stop checking the bound and only compares values.

Intuition

Picture flipping through an unsorted stack of cards looking for the seven of hearts. You have no choice but to turn them over one by one — there is no shortcut, because the cards are in no particular order. The moment you see it, you stop. If you reach the bottom without finding it, it is not in the stack. That is linear search: simple, always correct, and O(n).

The sentinel idea is like sliding a guaranteed seven of hearts under the bottom of the stack before you start. Now you can flip cards confidently without ever checking "is this the last card?" — you know a seven is coming. When you stop, you just ask one question: did I find it before the bottom (a real card) or was it the fake one I planted (meaning it was not really there)?

Walk through it

Step through the animation on the right. Phase 1 is plain linear search. The i pointer starts at index 0 and scans right. a[0] = 4 is not 7, so the cell turns visited and i advances. Same for a[1] = 2. At a[2] = 7 the value matches — the cell lights up as the hit and we return index 2.

Phase 2 is the sentinel variant. We reveal an extra cell after the array and copy the key 7 into it (the pivot-colored slot). Now i walks again, but this time the loop does no i < n check — it just compares values until one equals 7. It stops at index 2 exactly as before. Finally we restore the original last value and run a single test: is the stop index i = 2 less than n = 5? Yes, so it is a genuine match. Had the walk run all the way onto the sentinel (i == n), that would have meant the key was absent and we would return -1.

The code, line by line

def linear_search(a, x):
    for i in range(len(a)):
        if a[i] == x:
            return i
    return -1
 
def sentinel_search(a, x):
    n = len(a)
    last = a[n - 1]
    a[n - 1] = x          # plant the key
    i = 0
    while a[i] != x:      # no i < n check needed
        i += 1
    a[n - 1] = last       # restore the array
    return i if (i < n - 1 or last == x) else -1

• linear_search is the baseline: the for loop both advances i and bounds it, and line 3 is the value comparison. First match returns immediately; falling off the end returns -1.
• last = a[n - 1] saves the real final value before we overwrite it — we must put it back so the caller's array is unchanged.
• a[n - 1] = x plants the key in the last slot. This makes the upcoming while guaranteed to terminate.
• Line 12, while a[i] != x, is the whole point: it compares only values, with no bound check, because the planted key ensures a match always exists.
• a[n - 1] = last restores the array to its original contents.
• The final line decides real vs. fake hit. If i < n - 1, the match was strictly before the sentinel slot, so it is real. If i == n - 1, it could be the planted key or a genuine match in the last position — last == x disambiguates. Anything else means not found, so return -1.

Complexity

Both versions are O(n): the sentinel does not change the asymptotic cost. What it removes is one comparison (the i < n bound) on every iteration, which can be a measurable constant-factor win in a tight inner loop on large arrays. It is a classic micro-optimization, not an algorithmic one.

When to use / pitfalls

Practice