In this post we’ll see how to write Linear search or Sequential search program in Java. Linear search is considered the simplest searching algorithm but it is the slowest too because of the large number of comparisons.
How Linear search works
Linear search as the name suggests works by linearly searching the input array for the searched element.
- Compare the searched element with each element of the array one by one starting from the first element of the array.
- If the searched element is found return the index of the array where it is found. If searched element is not found with in the searched array then return -1.
Linear search Java program
Java program for linear search can be written in both recursive and iterative ways. We’ll see both of these solutions here.
Linear search in Java – Iterative program
In the Java program for linear search, user is prompted to enter the searched element. Then the array is traversed in a loop to find the element. If element is found in the array its index is returned otherwise -1 is returned.
public class LinearSearch {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[] arr = {12, 23, 10, 34, 55, 4, 68, 3, 73, 99};
System.out.println("Enter value to search: ");
int searchElement = sc.nextInt();
int index = linearSearch(arr, searchElement);
if(index != -1){
System.out.println("Searched item " + arr[index] + " found at index "+index);
}else{
System.out.println("Searched item " + searchElement + " not found in the array");
}
}
private static int linearSearch(int[] arr, int searchElement){
for(int i = 0; i < arr.length; i++){
if(arr[i] == searchElement){
return i;
}
}
return -1;
}
}
Output for few searches-
Enter value to search: 68 Searched item 68 found at index 6 Enter value to search: 8 Searched item 8 not found in the array Enter value to search: 10 Searched item 10 found at index 2
Linear search in Java – Recursive program
In the recursive linear search program, search method is called recursively with the next index. Exit condition is when index is greater than the last index of the array.
public class LinearSearch {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[] arr = {12, 23, 10, 34, 55, 4, 68, 3, 73, 99, 15};
System.out.println("Enter value to search: ");
int searchElement = sc.nextInt();
int index = linearSearch(arr, 0, arr.length - 1, searchElement);
if(index != -1){
System.out.println("Searched item " + arr[index] + " found at index "+index);
}else{
System.out.println("Searched item " + searchElement + " not found in the array");
}
}
private static int linearSearch(int[] arr, int index, int length, int searchElement){
// exit condition
if(index > length)
return -1;
// when searched element is found
if(arr[index] == searchElement){
return index;
}
return linearSearch(arr, index+1, length, searchElement);
}
}
Output for few searches-
Enter value to search: 12 Searched item 12 found at index 0 Enter value to search: 15 Searched item 15 found at index 10 Enter value to search: 34 Searched item 34 found at index 3 Enter value to search: 18 Searched item 18 not found in the array
Time and Space complexity of Linear search
Since comparison of elements is done linearly so average and worst time complexity of Linear search is O(n). Space complexity of linear search is O(1) for iterative solution as no extra space is needed. For recursive solution recursive method calls are stacked so in that case space complexity is O(n).
That's all for this topic Linear Search (Sequential Search) Java Program. If you have any doubt or any suggestions to make please drop a comment. Thanks!
>>>Return to Java Programs Page
Related Topics
You may also like-