Linear Search in Java

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 Time Complexity O(n) Best Case O(1) Worst Case O(n) Space Complexity O(1) Avg. Comparisons (n+1)/2

Algorithm to implement linear search in C++

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. Program to implement linear search algorithm in JAVA

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

}

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) O(1)

O(n)

O(n)

O(1)

Average Comparisions

(N+1)/2

2 comments on “Linear Search in Java”

• Nanda

explain how to calculate space complexity 10
• 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). 17