Linear search is a simple searching algorithm that sequentially checks each element in a list or array until the target element is found or the end of the list is reached. It works well for small lists or unordered collections. However, for large datasets, it’s not as efficient as other search algorithms like binary search, which are designed for sorted collections.
Here’s a basic explanation of how linear search works:
1. Start from the first element of the list.
2. Compare the target element with each element of the list sequentially.
3. If the target element is found, return its index.
4. If the end of the list is reached without finding the target element, return a sentinel value (e.g., -1) to indicate that the element is not present in the list.
Now, let’s see a simple implementation of linear search in Java:
public class LinearSearch {
public static int search(int[] arr, int target) {
// Iterate through each element in the array
for (int i = 0; i < arr.length; i++) {
// If the current element equals the target, return its index
if (arr[i] == target) {
return i;
}
}
// If the target is not found, return -1
return -1;
}
public static void main(String[] args) {
int[] arr = {10, 5, 7, 2, 15};
int target = 7;
// Perform linear search
int index = search(arr, target);
// Check if the target is found
if (index != -1) {
System.out.println("Element found at index: " + index);
} else {
System.out.println("Element not found in the array.");
}
}
}
In this implementation:
– The `search` method takes an array of integers (`arr`) and the target element (`target`) as parameters.
– It iterates through each element of the array using a for loop.
– If the current element matches the target, it returns the index of that element.
– If the end of the array is reached without finding the target, it returns -1.
– In the `main` method, we create an array and call the `search` method to find a target element (7 in this case). Then, we print the index if the target is found, or a message indicating that the element was not found.