What is Sentinel Linear Search?
In the basic linear search, we need to compare the target element with the every element in the array. The Sentinel linear search improves this by the appending the target element to end of the array. This way, we eliminate the need to the check for the end condition of the loop as the target will always be found.
Below is the Implementation of Sentinel Linear Search:
// Java Program for Implementation
// of Sentinel Linear Search
import java.io.*;
// Driver Class
public class GFG {
public static int sentinelLinearSearch(int[] arr, int target) {
int n = arr.length;
// Store the last element
int last = arr[n - 1];
// Append target to end of the array
arr[n - 1] = target;
int i = 0;
while (arr[i] != target) {
i++;
}
if (i < n - 1 || last == target)
return i;
// Target not found in the array
return -1;
}
// Main Function
public static void main(String[] args) {
int[] arr = { 4, 2, 7, 1, 9, 5 };
int target = 7;
int index = sentinelLinearSearch(arr, target);
if (index != -1) {
System.out.println("Element found at index: " + index);
} else {
System.out.println("Element not found");
}
}
}
Output
Element found at index: 2
Complexity of Sentinel Linear Search
Time Complexity:
Worst: O(n) Best: O(1) , found in first iteration
Average: O(n) , Average complexity will still be same as the key will be found afterwards.
Sentinel Linear Search in Java
The Linear search is a simple searching algorithm that checks every element in the list or array sequentially until the target element is found or the end of the list is reached. While linear search is not the most efficient search algorithm it is straightforward and works well for small datasets or unordered lists.
In this article, we will learn about Sentinel Linear Search in Java.
Linear Search in Java
In this approach, we iterate through the array from beginning to end comparing each element with the target element. If the element matches the target we return its index. If the end of the array is reached without finding the target we return -1 to indicate that the target is not present in the array.
Linear Search in Java:
// Java Program to Implement
// Linear Search
import java.io.*;
// Driver Class
public class GFG {
public static int linearSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
// Found the target element and return its index
if (arr[i] == target) {
return i;
}
}
// Target not found in the array
return -1;
}
// Main Function
public static void main(String[] args) {
int[] arr = { 4, 2, 7, 1, 9, 5 };
int target = 7;
int index = linearSearch(arr, target);
if (index != -1) {
System.out.println("Element found at index: " + index);
} else {
System.out.println("Element not found");
}
}
}
Output
Element found at index: 2