Working of Sentinal Linear Search in C

Here’s a step-by-step example to understand the working of Sentinel Linear Search.

Input

Array[] = [3, 5, 1, 8, 2]
Target =  8

Steps

1. Append the target element (8) at the end of the array as a sentinel. Array becomes: [3, 5, 1, 8, 2, 8]
2. Initialize a loop variable i to 0, representing the current index.
3. Compare the element at index 0 with the target element (8). No match (3 ≠ 8).
4. Increment the loop variable i to 1 and compare the element at index 1 with the target element (8). No match (5 ≠ 8).
5. Increment the loop variable i to 2 and compare the element at index 2 with the target element (8). No match (1 ≠ 8).
6. Increment the loop variable i to 3 and compare the element at index 3 with the target element (8). A match is found (8 = 8).
7. The search is successful, and the index (3) where the match was found is returned.

Output

The target element 8 is found at index 3 in the original array.

Sentinel Linear Search is basically a variation of the traditional linear search algorithm. It is designed to reduce the number of comparisons required to find a specific target value within an array or list. In this article, we will learn how to implement Sentinal Linear Search in C, see how it works, and compare its performance with traditional linear search.