Linear Search in Java

June 4, 2022

Linear Search in Java

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 only suitable to search for elements in a small and unsorted list of elements
Linear Search
Time ComplexityO(n)
Best CaseO(1)
Worst CaseO(n)
Space ComplexityO(1)
Avg. Comparisons(n+1)/2

Algorithm to implement linear search in Java

  1. Take input from the user for both the array & item to be searched. 
  2. Using a sequential loop compare each element in the array with the item.
  3. If at any index both matches, terminate and print found.
  4. Else continue comparison till the end of the array.
  5. If reached the end without a match, print Not Found.
Linear search in Java

Program to implement linear search algorithm in JAVA

Run 
class Main {

    private static void LinearSearch(int[] arr, int item) {

        for(int i=0;i < arr.length;i++){
            if(arr[i] == item)
            {
                System.out.println(item + " Found at index : " + i);
                return;
            }
        }
        System.out.println("Not found");

    }

    public static void main(String args[]) {
        int[] arr = {12, 5, 18, 25, -3, 19};

        int item = 25;
        LinearSearch(arr, item);
    }
}
// Space Complexity : O(N)
// Time Complexity : O(N)

Output

25 found at index : 3

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

Data Structures and Algorithm Learn Searching PrepInsta

Searching

Searching algorithms are easy to learn but are really important for college semester exams and companies offering package between 3 – 6 LPA would ask direct searching questions in online test/ interviews.

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