Back to: Java Tutorials
Explanation of Linear Search
Linear search is a simple search algorithm that iterates over a list of elements and compares each element with the target element until a match is found or the end of the list is reached.
To understand linear search, consider the following list of numbers: [5, 3, 8, 4, 2]. Suppose we want to find the position of the element 8 in the list. The linear search algorithm starts at the beginning of the list and compares each element with the target element until a match is found.
The figure below shows the linear search algorithm for finding the element 8 in the list [5, 3, 8, 4, 2]:
Index 0: 5 -> 8 not found yet
Index 1: 3 -> 8 not found yet
Index 2: 8 -> 8 found at index 2
As we can see from the figure, the linear search algorithm compares each element in the list with the target element until it finds a match at index 2, where the element 8 is located.
If the target element is not present in the list, the linear search algorithm will iterate over all the elements in the list and return a “not found” result. The figure below shows the linear search algorithm for finding the element 7 in the list [5, 3, 8, 4, 2]:
Index 0: 5 -> 7 not found yet
Index 1: 3 -> 7 not found yet
Index 2: 8 -> 7 not found yet
Index 3: 4 -> 7 not found yet
Index 4: 2 -> 7 not found yet
Not found
Another example:
The following figure illustrates the process of linear search for finding the number 7 in the list [5, 9, 3, 7, 1, 8]:
[5, 9, 3, 7, 1, 8]
^ (compare 5 with 7, no match)
^ (compare 9 with 7, no match)
^ (compare 3 with 7, no match)
^ (compare 7 with 7, match found)
As can be seen from the figure, linear search requires iterating through each element in the list, which can be time-consuming for very large lists. However, for small lists or lists that are not sorted, linear search can be a good option.
In summary, linear search is a simple search algorithm that iterates over a list of elements and compares each element with the target element until a match is found or the end of the list is reached. Linear search is easy to implement, but it can be slow for large lists as it has a time complexity of O(n), where n is the number of elements in the list.
Java Code Example on Linear Search
Here is an example of a linear search implementation in Java:
public class LinearSearch {
public static int search(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
return i; // Target found at index i
}
}
return -1; // Target not found
}
public static void main(String[] args) {
int[] arr = {5, 3, 8, 4, 2};
int target = 8;
int index = search(arr, target);
if (index != -1) {
System.out.println("Target found at index " + index);
} else {
System.out.println("Target not found");
}
}
}
In this implementation, the search
method takes an array of integers arr
and a target integer target
, and returns the index of the target in the array if found, or -1 if not found. The search
method iterates over each element in the array using a for loop, and checks if the current element is equal to the target. If the target is found, the method returns the index of the current element, which is the index of the target in the array. If the loop finishes without finding the target, the method returns -1 to indicate that the target was not found.
In the main
method, we create an example array arr
and set the target integer to 8. We then call the search
method with arr
and target
, and store the result in the index
variable. We then check if the index
is -1 or not, and print the appropriate message to the console.
Note that linear search has a time complexity of O(n), where n is the number of elements in the array, so it is not the most efficient algorithm for large arrays. However, it is a simple algorithm to understand and implement.
Also, see the example code JavaExamples_NoteArena in our GitHub repository. See complete examples in our GitHub repositories.
Follow us on social media
Follow Author