Is Sentinel Linear Search better than normal Linear Search?
Last Updated :
23 Dec, 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;
}
|
Java
import java.io.*;
class GFG {
static int linearSearch(int[] arr, int N, int X)
{
for (int i = 0; i < N; i++) {
if (arr[i] == X) {
return i;
}
}
return -1;
}
public static void main(String[] args)
{
int[] arr = { 2, 3, 4, 10, 40 };
int x = 10;
int N = arr.length;
int result = linearSearch(arr, N, x);
if (result == -1) {
System.out.print("Element not present");
}
else {
System.out.print("Element present at index "
+ result);
}
}
}
|
Python3
def linearSearch(arr, N, x):
for i in range(N):
if (arr[i] == x):
return i
return -1
if __name__ == "__main__":
arr = [ 2, 3, 4, 10, 40 ]
x = 10
N = len(arr)
result = linearSearch(arr, N, x)
if (result == -1):
print("Element not present")
else:
print("Element present at index",result)
|
C#
using System;
public class GFG {
static int linearSearch(int[] arr, int N, int X)
{
for (int i = 0; i < N; i++) {
if (arr[i] == X) {
return i;
}
}
return -1;
}
static public void Main()
{
int[] arr = { 2, 3, 4, 10, 40 };
int x = 10;
int N = arr.Length;
int result = linearSearch(arr, N, x);
if (result == -1) {
Console.Write("Element not present");
}
else {
Console.Write("Element present at index "
+ result);
}
}
}
|
Javascript
function linearSearch(arr, N, x)
{
for (let i = 0; i < N; i++)
if (arr[i] == x)
return i;
return -1;
}
let arr = [ 2, 3, 4, 10, 40 ];
let x = 10;
let N = arr.length;
let result = linearSearch(arr, N, x);
if (result == -1)
console.log("Element not present");
else
console.log("Element present at index ", result);
|
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;
}
|
Java
import java.io.*;
class GFG {
static void linearSearch(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))
System.out.print("Element present at index "
+ i);
else
System.out.print("Element not present");
}
public static void main(String[] args)
{
int[] arr = { 2, 3, 4, 10, 40 };
int key = 10;
int N = arr.length;
linearSearch(arr, N, key);
}
}
|
Python3
def sentinelSearch(arr, n, key):
last = arr[n - 1]
arr[n - 1] = key;
i = 0
while (arr[i] != key):
i=i+1
arr[n - 1] = last
if ((i < n - 1) or (arr[n - 1] == key)):
print("Element present at index",i)
else:
print("Element not present")
if __name__ == "__main__":
arr = [ 2, 3, 4, 10, 40 ]
N = len(arr)
key = 10
sentinelSearch(arr, N, key)
|
C#
using System;
public class GFG {
public static 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))
Console.WriteLine("Element present at index "
+ i);
else
Console.WriteLine("Element not present");
}
static public void Main()
{
int[] arr = { 2, 3, 4, 10, 40 };
int N = arr.Length;
int key = 10;
sentinelSearch(arr, N, key);
}
}
|
Javascript
function sentinelSearch(arr, n, key)
{
let last = arr[n - 1];
arr[n - 1] = key;
let i = 0;
while (arr[i] != key)
i++;
arr[n - 1] = last;
if ((i < n - 1) || (arr[n - 1] == key))
console.log("Element present at index ", i);
else
console.log("Element not present");
}
let arr = [ 2, 3, 4, 10, 40 ];
let N = arr.length;
let key = 10;
sentinelSearch(arr, N, key);
|
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.
Please Login to comment...