It is commonly referred to as sequential search. This algorithm is essential for locating a specific element within an array or list of elements. The time complexity of linear search is O(n). In the best-case scenario, the time complexity is O(1), while in the worst-case scenario, it is O(n), where n represents the total number of elements in the list or array.
Sentinel Linear Search:
It presents a modification to the linear search method by incorporating a sentinel value, a unique value positioned at the array's conclusion. This serves as the termination condition, eradicating the necessity to verify the array's end during iteration. This enhancement results in a more efficient time complexity compared to standard linear search implementations.
Example:
Let's consider a C program to demonstrate the Sentinel linear search algorithm:
#include <stdio.h>
int sentinelLinearSearch(int arr[], int n, int target) {
int last = arr[n - 1]; // Store the last element
arr[n - 1] = target; // Place the sentinel at the end
int i = 0;
while (arr[i] != target) {
i++;
}
arr[n - 1] = last; // Restore the last element
if (i < n - 1 || arr[n - 1] == target) {
return i;
} else {
return -1;
}
}
int main() {
int arr[] = {5, 8, 12, 15, 21, 27, 34, 42};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 15;
int result = sentinelLinearSearch(arr, n, target);
if (result != -1) {
printf("Element %d found at index %d\n", target, result);
} else {
printf("Element %d not found in the array\n", target);
}
return 0;
}
Output:
Element [value] found at index [value]
Element [value] not found in the array
Explanation:
In this software, a special value is temporarily inserted at the end of the array to optimize the search process without requiring an additional validation step inside the loop. The procedure scans through the array until it locates the desired value. Upon completing the search, the placeholder is substituted with the initial last item. Following this, the primary function sets up an array and showcases the application of the sentinel linear search to determine the position of a specific element. This offers a precise indication of the element's existence in the array and its corresponding index.
Example 2:
Let's consider a C program to determine the execution time of sentinel linear search compared to the conventional linear search.
#include <stdio.h>
#include <time.h>
#define ARRAY_SIZE 1000000
#define TARGET_VALUE 999999
int linearSearch(int arr[], int size, int target) {
for (int i = 0; i < size; i++) {
if (arr[i] == target) {
return i;
}
}
return -1;
}
int sentinelLinearSearch(int arr[], int size, int target) {
int last = arr[size - 1];
arr[size - 1] = target;
int i = 0;
while (arr[i] != target) {
i++;
}
arr[size - 1] = last;
if (i < size - 1 || arr[size - 1] == target) {
return i;
} else {
return -1;
}
}
double measureExecutionTime(int arr[], int size, int target, int (*searchFunction)(int[], int, int)) {
clock_t start_time, end_time;
start_time = clock();
int result = searchFunction(arr, size, target);
end_time = clock();
double execution_time = ((double)(end_time - start_time)) / CLOCKS_PER_SEC;
return execution_time;
}
int main() {
int arr[ARRAY_SIZE];
for (int i = 0; i < ARRAY_SIZE; i++) {
arr[i] = i;
}
int target = TARGET_VALUE;
double linearSearchTime = measureExecutionTime(arr, ARRAY_SIZE, target, linearSearch);
printf("Time taken by linear search: %lf seconds\n", linearSearchTime);
double sentinelSearchTime = measureExecutionTime(arr, ARRAY_SIZE, target, sentinelLinearSearch);
printf("Time taken by sentinel linear search: %lf seconds\n", sentinelSearchTime);
double timeSaved = linearSearchTime - sentinelSearchTime;
printf("Time saved by using sentinel linear search: %lf seconds\n", timeSaved);
return 0;
}
Output:
Element [value] found at index [value]
Element [value] not found in the array
Explanation:
- linearSearch Function:
The linearSearch function executes the conventional linear search algorithm by sequentially scanning through an array to locate the desired value. It provides the index of the target if it is located, or -1 if the target value is not found.
- sentinelLinearSearch Function:
The sentinelLinearSearch method enhances the linear search algorithm by incorporating a sentinel element at the array's conclusion. This improvement facilitates the search process by promptly halting it upon locating the desired value within the array. If the target value is discovered, the function outputs the respective index; if not, it returns -1.
- measureExecutionTime Function:
The measureExecutionTime function determines the running duration of a specified search algorithm by utilizing the clock Function to record the time before and after the search process, yielding the elapsed time in seconds. This feature enables the comparison of performance across various search algorithms.
- Main Function:
The primary function starts by creating an array and then proceeds to calculate the running time for both linear search and sentinel linear search methods using the measureExecutionTime function. It displays the time taken for each search technique and highlights the time efficiency improvement gained from implementing the sentinel linear search approach, providing valuable information on optimization effectiveness.