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;
      }
      return "Given element is not found in the array.";
    }
}

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