Tuesday, February 5, 2019

Linear Search (Sequential Search) Java Program

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.

  1. Compare the searched element with each element of the array one by one starting from the first element of the array.
  2. 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 in Java

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 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

  1. Binary Search Program in Java
  2. Bubble Sort Program in Java
  3. Tree Sort in Java Using Binary Search Tree
  4. Factorial Program in Java
  5. Find Duplicate Characters in a String With Repetition Count - Java Program

You may also like-

  1. Array Rotation Java Program
  2. How to Convert Date And Time Between Different Time-Zones in Java
  3. Write to a File in Java
  4. Producer-Consumer Java Program Using volatile
  5. Difference Between ArrayList And LinkedList in Java
  6. Optional Class in Java With Examples
  7. Generic Class, Interface And Generic Method in Java
  8. String join() Method And StringJoiner Class in Java