Boost Search Speed in C++ Arrays and Strings with the Sentinel Technique

When searching for an element in an integer array or a character in a string, the straightforward linear scan using a for loop works but performs an extra boundary check on each iteration. For large collections this overhead can be noticeable.

The sentinel method eliminates the repeated i < n test by temporarily placing the target value at the end of the container, guaranteeing that the loop will always find a match and thus can run without explicit bounds checking.

Original naïve implementations

int find(int A[], int n, int element) {
    for (int i = 0; i < n; i++) {
        if (A[i] == element) return i;
    }
    return -1;
}

int find(string& str, char c) {
    for (int i = 0; i < str.length(); i++) {
        if (str[i] == c) return i;
    }
    return -1;
}

Sentinel‑based versions

For an integer array:

int find1(int A[], int n, int element) {
    if (n <= 0) return -1;
    if (A[--n] == element) return n; // element already at last position
    int hold = A[n];
    A[n] = element;               // place sentinel
    int i = 0;
    for (;;) {
        if (A[i] == element) break;
        i++;
    }
    A[n] = hold;                  // restore original last element
    return i < n ? i : -1;
}

For a string:

int find1(string& str, char c) {
    int n = str.length();
    if (n <= 0) return -1;
    if (str[--n] == c) return n;
    char hold = str[n];
    str[n] = c;                   // sentinel
    int i = 0;
    for (;;) {
        if (str[i] == c) break;
        i++;
    }
    str[n] = hold;                // restore
    return i < n ? i : -1;
}

The core idea is to append the search key as a sentinel at the last position, so the loop can run indefinitely until a match is found; the sentinel guarantees termination without an explicit range check.

Performance test

The following test measures execution time for 10,000 searches of the value 1 in an array of 200,000 integers, comparing the original find with the sentinel version find1:

void testFind() {
    int N = 200000;
    int* A = new int[N];
    A[N-2] = 1;
    DWORD start = ::GetTickCount64();
    for (int i = 0; i < 10000; i++)
        find(A, N, 1);
    DWORD end = ::GetTickCount64();
    cout << "优化前：" << end - start << " 毫秒" << endl;

    start = ::GetTickCount64();
    for (int i = 0; i < 10000; i++)
        find1(A, N, 1);
    end = ::GetTickCount64();
    cout << "优化后：" << end - start << " 毫秒" << endl;
}

The test output (illustrated by the image) shows a modest reduction in elapsed time, confirming that the sentinel technique can speed up searches when the data set is large.

In summary, by adding a sentinel element at the end of an array or string, the algorithm removes the per‑iteration boundary check, potentially improving performance for large collections, though for very small arrays the overhead of the extra assignments may outweigh the benefit.