Yes, this is another search method besides linear search and binary search. 😉😉

Difference between linear, binary and sentinel linear search.

Linear Search	Binary Search	Sential Linear Search
The element does not need to be in sorted order.	The element must be sorted.	The element does not need to be in sorted order.
Time complexity in the worst-case scenario is O(n).	Time complexity in the worst-case scenario is O(log(n)).	Time complexity in the worst-case scenario is O(n).
The actual time complexity is 2N+1: one N for comparison and another N for condition checking.	It takes log(n) time.	It takes N steps for comparison and another 2 steps for the if-else condition check. So, the actual time complexity is O(N+2).

Algorithm

Start

Input the list arr[] of size n and the target element key

Store the last element of arr[] in a variable lastElement

Replace the last element of arr[] with key (sentinel step)

Initialize i = 0

Repeat while arr[i] ≠ key:
a. Increment i by 1

Restore the last element of arr[] by setting arr[n-1] = lastElement

If i < n-1 or arr[n-1] == key, then:
a. Print "Element found at index i"
Else:
a. Print "Element not found"

End

Code:

int last = array[n-1];
    array[n-1] = target;
    int i = 0;
    while(array[i] != target) {
        i++;
    }
    array[n-1] = last;
    cout << ((i < n - 1 or a[n - 1] == target) ? "Element Found" : "Element Not Found");

Visualtionztion of Sential Search:

Orginal Array:

The target element is 8. So, change the last element to the target element.

Updated array:

Now, initialize i = 0 and start a while loop to check for the target element.

In the first iteration, it checks at index zero. Since 1 ≠ 8, i increments to 1.

In the second iteration, it checks at index one. Since 2 ≠ 8, i increments to 2.

It continues checking until the last element of the array.

In the seventh iteration, it checks at index six. Since 8 = 8, it stops.

The last element of the array is restored. The updated array will look like this:

It will check if the condition i < n - 1 or if the last element of the array is equal to the target element.

The target element might be found before the last index.
The target element might be at the last index.

In both cases, the condition will be true, and the output will follow the program logic.
Otherwise, it will output according to the program.

Time Complexity Analysis

Linear search worst case	Sentail Linear Search worst case
3n+2	2n+3

I hope you like the explanation. Feel free to send your feedback to abuharish186@gmail.com.

Sentinel Linear Search: Enhancing Search Efficiency