Question

write a Linear Search algorithm using sentinel approach? How can the sentinel linear search improve the performance over the standard linear search?

Answer 1

Linear Search :
The Concept of linear search tells us to compare the search key with the
elements in the array one by one (using a loop) and end the loop as soon as
we get the first copy of the search key in the array.

Now lets take a look at the worst case of linear search in which the search
key that is not present in the array of size N then the Simple Linear Search
will take a total of 2N+1 comparisons

(N comparisons against every element in the search array, the if condition
in for loop, and N+1 comparisons to test the for loop condition,
where we check the index of the array).

//n+1 comparisons for checking whether i < l
for (int i = 0; i < length; i++) {

   //n comparisons of checking if element found
if (array[i] == element) {
return i; // I found the position of the element requested
}
}

Sentinel Linear Search :

Here the idea is to reduce the number of comparisons required to find an
element in a array.

Here we replace the last element of the
array with the search key itself and run a while loop to see if
there exists any element equal to the search key in the array and quit
the loop as soon as we find the search key.

int item = array[N-1];   
// Here item is the search element.
int i = 0;
//only one comparison is required for each iteration
//so in worst case n comparisons are required.
while(array[i]!=item)   
{
i++;   
}
if( (i < N-1))
{
cout << " Item Found @ "<<i;
}
else
{
cout << " Item Not Found";   
}