C Program for Sentinel Linear Search | Time Complexity of Sentinel Linear Search | Coding Expert 10

Accept n values in array from user. Accept a value x from user and use sentinel linear search algorithm to check whether the number is present in the array or not and output the position if the number is present.

Sentinel search is a type of linear search where the number of comparisons is reduced as compared to a traditional linear search. The value to be searched can be appended to the list at the end as a “sentinel value.

Sentinel Search Algorithm: 

Step 1: Start

Step 2: Accept n numbers in an array num and a number to be searched 

Step 3: set i=0, last=num[n-1], num[n-1]=number

Step 4: Compare num[i] and number If equal then goto step 6

Step 5: i=i+1 and goto step 4 

Step 6: num[n-1]=last 

Step 7: if (num[i]=number) then Print “Required number is found at location i+1” else Print “Require data not found” 

Step 8: Stop

Time Complexity: 

Base Case: O(1) 

Worst Case: O(n) 

Average Case: O(n)

SENTINEL SEARCH :

#include<stdio.h>
#define max 10

int main()
{
int a[max],k,i,n,flag=0,index;
printf("Enter Size of array:");
  scanf("%d",&n);
generate(a,n);
printf("Random elements are\n");
   for(i=0;i<n;i++)
      printf("%d\n",a[i]);

printf("Enter number to search: ");
   scanf("%d",&k);
Sentinelsearch(a,n,k);
}
void generate(int a[],int n)
{
int i;
for(i=0;i<n;i++)
   a[i]=rand()%100;

}
void Sentinelsearch(int a[],int n,int k)
{
int i,flag=0,index ;
i=0;
a[n]=k;
while(a[i]!=k)
    i++;
if(i<n)
    printf("Searched found at index %d",i+1);
else
    printf("Not Found");

}

Output :

Enter Size of array:7
Random elements are
41
67
34
0
69
24
78
Enter number to search: 69
Searched found at index 5
Process returned 0 (0x0)   execution time : 9.575 s
Press any key to continue.