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.org/sentinel-linear-search/
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.