Linear Search in Java

Linear Search

What is a linear search?

Linear Search is a sequential search algorithm. In Linear Search we’ll have to traverse the array comparing the elements consecutively one after the other until the target value is found. Linear Search has a high time complexity making at most n comparison hence, it is suitable to search for elements in small and unsorted list of elements.

Implementation of Linear Search

  • Step 1:  Take the input from the user.
  • Step 2: Create a function for the search to be carried out.
  • Step 3: Create a for loop in the above created function that will start from i = 0 to the last index of the array that is Array Length-1.
  • Step 4: Compare every element with the target element.
    If element is found return i , where i is the index of searched element.
  • Step 5: If element is not found after traversing through the list, return -1 with a message of unsuccessful search.

Algorithm to implement linear search in JAVA

  1. int Search(Arr[] , Search Element)
  2. FOR i = 0, i -> Arr[].length
  3. IF (Arr[i] == Search Element)
    return i;
  4. END of FOR
  5. return -1
JAVA Program for Linear Search

Program to implement linear search algorithm in JAVA

import java.util.*;
public class Main 
{  
public static int search(int ar[], int s) 
{ 
    int l = ar.length; 
    for(int i = 0; i < l; i++) 
    { 
        if(ar[i] == s) 
            return i; 
    } 
    return -1; 
} 
public static void main(String args[]) 
{ 
    int ar[] = { 2, 3, 4, 10, 40 };
    System.out.println("Enter a number you want to search for - ");
    Scanner s= new Scanner(System.in);
    int num=s.nextInt();
    int result = search(ar, num)+1; 
    if(result == -1) 
        System.out.print("Element not found."); 
    else
        System.out.print("Element found at index " + result); 
} 
} 
Enter a number you want to search for -
3
Element found at index 2

Linear Search vs Binary Search

Binary search is much faster than linear search, while the former has time complexity of Log(n) the later has O(n)

Linear Search in Java meme

Time Complexity
For Linear Search

Best

O(1)

Average

O(n)

Worst

O(n)

Space Complexity

O(1)

Average Comparisions

(N+1)/2

2 comments on “Linear Search in Java”


    • Lalit Kumar Baghel

      time complexity is calculated by the number of lines that will be executed at run-time depending on the number of inputs.
      space complexity is calculated by the number of more variables required to execute the program.

      here the line written in the for loop will be executed n(number of inputs) times, so time-complexity is O(n).
      and we require two(a constant number of) variables during the execution of the whole program, so space-complexity is O(1).