Select Page

Is Sentinel Linear Search better than normal Linear Search?

Team 1 - Programming
Published: November 21, 2022

What is Sentinel Linear Search?

Sentinel Linear search is a type of linear search where the element to be searched is placed in the last position and then all the indices are checked for the presence of the element without checking for the index out of bound case.

The number of comparisons is reduced in this search as compared to a traditional linear search. When a linear search is performed on an array of size N then in the worst case a total of N comparisons are made when the element to be searched is compared to all the elements of the array and (N + 1) comparisons are made for the index of the element to be compared so that the index is not out of bounds of the array which can be reduced in a Sentinel Linear Search. So total comparisons in the worst case can be 2*N + 1.

But in this search, the last element of the array is replaced with the element to be searched and then the linear search is performed on the array without checking whether the current index is inside the index range of the array or not because the element to be searched will definitely be found inside the array even if it was not present in the original array. So, the index to be checked will never be out of the bounds of the array. The number of comparisons in the worst case there will be (N + 2).

Implementations:

See below the implementations of both the searching algorithm:

Implementation of Linear Search:

C++

  

#include <bits/stdc++.h>

using namespace std;

  

int linearSearch(int arr[], int N, int x)

{

    for (int i = 0; i < N; i++)

        if (arr[i] == x)

            return i;

    return -1;

}

  

int main()

{

    int arr[] = { 2, 3, 4, 10, 40 };

    int x = 10;

    int N = sizeof(arr) / sizeof(arr[0]);

  

    

    int result = linearSearch(arr, N, x);

    if (result == -1)

        cout << "Element not present";

    else

        cout << "Element present at index " << result;

  

    return 0;

}

Output

Element present at index 3

Time Complexity: O(N)
Auxiliary Space: O(1)

Implementation of Sentinel Linear Search:

Below are the steps to implement the algorithm:

  • In sentinel search, we first insert the target element at the end of the list, and after that we compare each item of the list until we find our required item.
    • Either the required item is in the list, in that case it will be found before we reach the end of the list. 
    • Or the list didn’t have the target element, so the algorithm will reach the end of the list and find the target element that we have inserted initially.
  • Here, we have to do only one comparison, we only need to check if the element matches the target item or not, and we don’t need to check if we go out of the list.
  • Finally, check if the item we found was already there in the list or was added by us at the end of the list.
  • This check will happen only one time after the end of the loop.

Below is the code to implement the steps.

C++

  

#include <bits/stdc++.h>

using namespace std;

  

void sentinelSearch(int arr[], int n, int key)

{

    

    int last = arr[n - 1];

  

    

    

    arr[n - 1] = key;

    int i = 0;

  

    while (arr[i] != key)

        i++;

  

    

    arr[n - 1] = last;

  

    if ((i < n - 1) || (arr[n - 1] == key))

        cout << "Element present at index " << i;

    else

        cout << "Element not present";

}

  

int main()

{

    int arr[] = { 2, 3, 4, 10, 40 };

    int N = sizeof(arr) / sizeof(arr[0]);

    int key = 10;

  

    

    sentinelSearch(arr, N, key);

  

    return 0;

}

Output

Element present at index 3

Time Complexity: O(N)
Auxiliary Space: O(1)

Conclusion:

In Sentinel Linear Search, we are doing one less comparison in each step. So the time complexity is remarkably cut down. As mentioned earlier, we can see that in the worst case a traditional linear search utilizes 2*N+1 comparisons whereas the Sentinel linear search performs only N+2 comparisons.

So we can conclude that Sentinel Linear Search is better than normal Linear Search.

Source: www.geeksforgeeks.org