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

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

O(1)

O(n)

O(n)

O(1)

(N+1)/2

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

• Nanda

explain how to calculate space complexity

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