C Program for Sentinel Linear Search
Below is the implementation of the above approach:
C
// C program to implement sentinal linear search #include <stdio.h> int sentinelLinearSearch(int arr[], int size, int target) { // Storing the last element in temporary variable int last = arr[size - 1]; // Setting the sentinel to the target arr[size - 1] = target; int i = 0; while (arr[i] != target) { i++; } // Restore the original value at the end arr[size - 1] = last; // checking if last element is target or not if (i < size - 1 || arr[size - 1] == target) { return i; // Element found at index i } else { return -1; // Element not found } } // driver code int main() { int arr[] = { 3, 5, 1, 8, 2 }; int size = sizeof(arr) / sizeof(arr[0]); int target = 8; int result = sentinelLinearSearch(arr, size, target); // printing result based on the value returned by // sentinalLinearSearch if (result != -1) { printf("Element %d found at index %d\n", target, result); } else { printf("Element %d not found\n", target); } return 0; } |
Output
Element 8 found at index 3
Complexity Analysis
Time Complexity: O(N)
Auxiliary Space: O(1)
C Program For Sentinel Linear Search
Sentinel Linear Search is basically a variation of the traditional linear search algorithm. It is designed to reduce the number of comparisons required to find a specific target value within an array or list. In this article, we will learn how to implement Sentinal Linear Search in C, see how it works, and compare its performance with traditional linear search.