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.
What is Sentinel Linear Search?
In a typical linear search, you would check each element of an array one by one until you find the target value or reach the end. This means that in the worst-case scenario, you would make N comparisons, where N is the number of elements in the array.
However, Sentinel Linear Search uses an extra value to make the process faster. Instead of just searching through the array, it adds a special “sentinel” value at the end of the array. This sentinel value is set to be equal to the target value you’re looking for.
It eliminates the need to check for boundary conditions during each iteration of the search loop in the traditional linear search as you would have to ensure that you don’t go beyond the array’s bounds when checking elements. With the sentinel in place, you’re guaranteed that the index you’re checking will always fall within the array’s boundaries because the sentinel value is a valid element.
So, this sentinel value acts as a marker, thus making the search process more efficient. It doesn’t change the worst-case time complexity, which is still O(n) like the regular linear search, but it significantly reduces the actual number of comparisons made in practice. This reduction in comparisons leads to improved performance, especially when dealing with large datasets.
Prerequisites: Before implementing Sentinel Linear Search in C, you should have a basic understanding of:
- C programming language fundamentals.
- Arrays in C.
- Basic knowledge of loops and conditionals.
Working of Sentinal Linear Search in C
Here’s a step-by-step example to understand the working of Sentinel Linear Search.
Input
Array[] = [3, 5, 1, 8, 2] Target = 8
Steps
- Append the target element (8) at the end of the array as a sentinel. Array becomes: [3, 5, 1, 8, 2, 8]
- Initialize a loop variable i to 0, representing the current index.
- Compare the element at index 0 with the target element (8). No match (3 ≠ 8).
- Increment the loop variable i to 1 and compare the element at index 1 with the target element (8). No match (5 ≠ 8).
- Increment the loop variable i to 2 and compare the element at index 2 with the target element (8). No match (1 ≠ 8).
- Increment the loop variable i to 3 and compare the element at index 3 with the target element (8). A match is found (8 = 8).
- The search is successful, and the index (3) where the match was found is returned.
Output
The target element 8 is found at index 3 in the original array.
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; } |
Element 8 found at index 3
Complexity Analysis
Time Complexity: O(N)
Auxiliary Space: O(1)
Sentinel Linear Search Vs Traditional Linear Search
The below table lists the major differences between Sentinel Linear Search and Traditional Linear Search:
Sentinel Linear Search |
Traditional Linear Search |
---|---|
It uses an extra element called sentinel value that is placed at the end of the list or array to simplify the loop logic. | It does not use an extra element to determine if the end of the list is reached, instead, it uses a condition to check for bound of the array. |
It is faster to execute because it uses less number of comparisons than linear search. | It has a slightly slower performance due to more number of comparisons. |
The code is easier to read because you don’t have to add extra checks to see if you’ve reached the end of the list. | You have to include extra checks in your code to see if you’ve reached the end of the list in linear search. This can make your code messier and harder to understand. |
Performance Comparision between Sentinel Linear Search and Traditional Linear Search
Let’s take an example of a traditional linear search that searches for an element in a large dataset and see the time needed for execution.
Traditional Linear Search:
C
// C program to find the execution time of traditional // linear search #include <stdio.h> #include <time.h> // array with large number of elements #define ARRAY_SIZE 1000000 #define TARGET_VALUE 999999 // Traditional Linear Search int linearSearch( int arr[], int size, int target) { for ( int i = 0; i < size; i++) { if (arr[i] == target) { return i; // Found the target value at index i } } // Target value not found in the array return -1; } // driver code int main() { int arr[ARRAY_SIZE]; // Initialize the array with sorted values from 0 to // ARRAY_SIZE - 1 for ( int i = 0; i < ARRAY_SIZE; i++) { arr[i] = i; } // target is already the last value of array int target = TARGET_VALUE; // Measure the execution time clock_t start_time, end_time; start_time = clock (); // Perform the sentinel search int result = linearSearch(arr, ARRAY_SIZE, target); end_time = clock (); // Calculate the execution time in seconds double execution_time = (( double )(end_time - start_time)) / CLOCKS_PER_SEC; // Print the execution time printf ( "Time taken by sentinel Search: %lf seconds\n" , execution_time); return 0; } |
Output
Time taken by sentinel Search: 0.003044 seconds
Now, let’s consider the same dataset and use a sentinel linear search instead and see the execution time.
Sentinel Linear Search:
C
// C program to find the execution time of sentinal linear // search #include <stdio.h> #include <time.h> #define ARRAY_SIZE 1000000 #define TARGET_VALUE 999999 // Sentinel Linear Search int sentinelSearch( int arr[], int size, int target) { int lastValue = arr[size - 1]; arr[size - 1] = target; int i = 0; while (arr[i] != target) { i++; } arr[size - 1] = lastValue; if (i < size - 1 || arr[size - 1] == target) { return i; // Found the target value at index i } else { return -1; // Target value not found in the array } } // driver code int main() { int arr[ARRAY_SIZE]; // Initialize the array with sorted values from 0 to // ARRAY_SIZE - 1 for ( int i = 0; i < ARRAY_SIZE; i++) { arr[i] = i; } // target is already the last value of array int target = TARGET_VALUE; // Measure the execution time clock_t start_time, end_time; start_time = clock (); // Perform the sentinel search int result = sentinelSearch(arr, ARRAY_SIZE, target); end_time = clock (); // Calculate the execution time in seconds double execution_time = (( double )(end_time - start_time)) / CLOCKS_PER_SEC; // Print the execution time printf ( "Time taken by sentinel Search: %lf seconds\n" , execution_time); return 0; } |
Output
Time taken by sentinel Search: 0.002660 seconds
As we can see, the time taken by sentinal linear search is less than the time taken by traditional linear search.
Why Traditional Linear Search is still preferred over Sentinal Linear Search?
The Traditional Linear Search is still preferred over Sentinal Linear Search even after being efficient in performance due to the following reasons:
- Modification of data in a shared array or immutable data is not possible or may result in errors.
- Brach Prediction due to which some loop conditions are faster to evaluate than others.
For more details about Sentinel Linear Search, refer www.w3wiki.net/sentinel-linear-search/