Linear Search in Java

Linear search is a sequential searching algorithm in which we need to start from first element and check every element of the list until the desired key element is found. Since Linear search is slower than binary search and hashing it is less used nowadays.

Linear Search Algorithm

Syntax :

LinearSearch(arrayList, keyElement)
  for each item in the arrayList
    if item == value
      return its index

Steps :

1) Declare an array and search element as key.
2) Traverse through the array until the number is found.
3) If the key element is found, return the index position of the array element
4) If the key element is not found, return -1

Linear Search Complexities

Time Complexity: O(n)
The time complexity of linear search is O(n), where n is the number of elements in the array. Because in the worst-case scenario, the algorithm has to check every element once.

Space Complexity: O(1)
The space complexity is O(1) because the algorithm uses a constant amount of additional space, regardless of the input size.

Best Case
The best-case time complexity is O(1) that occurs when the target element is at the first position in the array.

Advantages of Linear Search Algorithm:

1) Linear search can be used irrespective of whether the array is sorted or not. It can be used on arrays of any data type.
2) Does not require any additional memory.
3) It is a well-suited algorithm for small datasets.

Disadvantages of Linear Search Algorithm:

1) On average, it requires checking half of the elements (O(n/2)) and, in the worst case, all elements (O(n)),so linear search has a time complexity of O(N) making it slow for large datasets.
2) Linear Search is not suitable for large arrays.

Applications of Linear Search Algorithm:

1) Unsorted Lists
2) Small Data Sets
3) Searching in Linked Lists

Program 1 :

public class LinearSearchProg1 {

	public static int linearSearch(int arr[],int x)
    {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == x)
                return i;
        }
        return -1;
    }

    public static void main(String args[])
    {
        int arr[] = { 26, 48, 80, 56, 37 };
        int x = 80;

        int result = linearSearch(arr , x);
        if (result == -1)
            System.out.print( "Element is not present in array");
        else
            System.out.print("Element is present at index " + result); // Indexing in Java array starts from zero
    }
}

Output :
Element is present at index 2

Program 2 :

import java.util.Scanner;

public class LinearSearchProg2 {

	public static void main(String args[])  
	  {  
	    int newArrayLength, currentArrayLength, keyElement, array[];  
	   
	    Scanner in = new Scanner(System.in);  
	    System.out.println("Enter number of elements");  
	    currentArrayLength = in.nextInt();   
	    array = new int[currentArrayLength];  
	   
	    System.out.println("Enter those " + currentArrayLength + " elements");  
	   
	    for (newArrayLength = 0; newArrayLength < currentArrayLength; newArrayLength++)  
	      array[newArrayLength] = in.nextInt();  
	   
	    System.out.println("Enter value to find");  
	    keyElement = in.nextInt();  
	   
	    for (newArrayLength = 0; newArrayLength < currentArrayLength; newArrayLength++)  
	    {  
	      if (array[newArrayLength] == keyElement)  
	      {  
	    	  System.out.println(keyElement + " is present at location " + (newArrayLength) + ".");  // Indexing in Java array starts from zero
	          break;  
	      }  
	   }  
	   if (newArrayLength == currentArrayLength)
	      System.out.println(keyElement + " isn't present in array.");  
	  } 
}

Output :

Enter number of elements
6
Enter those 6 elements
93
48
76
28
49
82
Enter value to find
49
49 is present at location 4.