C Program for Sentinel Search ..

What is Sentinel Search?

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

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)

C Program For Sentinel Search:

#include<stdio.h>

#define max 100

int main()

{

    int a[max],n,i,key;

    printf("Enter Size of Array:");

    scanf("%d",&n);

    printf("Enter Array Element:");

    for(i=0; i<n; i++)

        scanf("%d",&a[i]);

    printf("Array:\n");

    for(i=0; i<n; i++)

        printf("%d\n",a[i]);

    printf("Enter Key To Search:");

    scanf("%d",&key);

    sentinelsearch(a,n,key);

}

sentinelsearch(int a[max],int n,int key)

{

    int i,last;

    last=a[n-1];

    a[n-1]=key;

    i=0;

    while(a[i]!=key)

       i++;

    a[n-1]=last;

    if(a[i]==key)

    {

        printf("Search found at index %d",i+1);

    }

    else

    {

        printf("Not found");

    }

}

Output:

Enter Size of Array:5
Enter Array Element:2 3 4 5 6
Array:
2
3
4
5
6
Enter Key To Search:6
Search found at index 5

Explanation:

In Sentinel Search Function, We pass Array,'n',and 'key'.

we store last element of array in a variable

name 'last'.i.e last=a[n-1]

Why we did this?Because in next step we are replacing a[n-1] with key.

a[n-1]=key;

After this We initialize i=0 and we use while loop ,in while loop we have given condition that until we find a[i]==key,we will increment i.

If key value is found in array,while loop will stop...

if key value match is not found ,while loop will stop when it will reach n-1 position because we have replaced a[n-1] with key element.

After while loop stops we will again replace a[n-1] with its original number ,which was stored in 'last' variable.

a[n-1]=last

All this we are doing to stop while loop 

to increment i.

Please send your question using question form:)