# Linear Search Algorithm

Linear Search is one of the search algorithms to find a given element in a list of elements. This algorithm traverses every element in the list sequentially until a matching element is found or till the end of the list.

It is best suited for small collections when we have to search the element in a collection of less number of elements. For large arrays or collections, it is not a good search algorithm and may perform poorer in most scenarios.

## 1. Linear Search Algorithm

Let us begin with understanding the basics of the linear search.

### 1.1. How does Linear Search work?

In linear search, we traverse the array/collection sequentially. And we compare each element with the given search element as shown in the below image.

We will stop traversing if we find a match; otherwise, we will traverse the entire list of elements.

For above example, we have the elements `3,4,1,7,5` and we are searching for the element with value `7`. We will start traversing and comparing each element, first 3 with 7, 4 with 7, 1 with 7, and 7 with 7.

As soon as a match is found, we will stop traversing and return the index since we found the match.

### 1.2. Steps

``````LinearSearch(array, element)
for each item in the array
if item == value
return its index``````
1. Declare and initialize an array and search element.
2. Traverse the array until the search element is found.
3. If the given search element is found, return true or index of the element.
4. If the given search element is NOT found in the array, return false.

Let us understand more with an example.

## 2. Implementing Linear Search in Java

In the following example, we are:

• declaring and initializing an array of elements `arr`.
• searching the element `7` in the given array `arr`, we will start by assigning it to variable `ele`.
• getting the array length and assign it to variable `n`. We will use this length to run the for loop to traverse all the elements in the array `arr`.
• defining `lnrSearch()` method which accepts `array`, `length of the array`, and `search element` as a parameter and return an appropriate message.
• checking if the current element is equal to the argument element or not, in the for loop. If it matches then we return that the element is found. If the element is not found after traversing the entire array, we return that the given element is not found in the array.
``````class LinearSearch {
public static void main( String args[] ) {

//given an array of elements
int[] arr = { 3, 4, 1, 7, 5 };

//given search element
int ele = 7;

//get length of the array
int n = arr.length;

//call lnrSearch method and display returned result
System.out.println(lnrSearch(arr, n, ele));
}

//method to check for a element using linear search
static String lnrSearch(int arr[], int n, int ele){
for (int i = 0; i < n; i++) {
//checks for matching element
if (arr[i] == ele)
return "Given element is found at the index "+ i;
}
}
}``````

## 3. Time and Space Complexity

### 3.1. Time Complexity

• The linear search algorithm takes `O(1)` time complexity if the element is found at the index `0`. This is its best-case scenario.
• It takes O(n) time complexity for other cases where n if the position of the element in the array.
• In the worst case, the time complexity will be O(length) where length is the size of an array. It is a worst-case scenario.

### 3.2. Space Complexity

Since we are not using extra space. The linear search algorithm takes `O(1)` space complexity.

## 4. Conclusion

In this tutorial, we learned about the linear search algorithm and understood it with an example. We also learned its best-case and worst-case scenarios in terms of time and space complexity.

Happy Learning !!

Sourcecode on Github