Linear Search

Intro

Linear search is a fairly simple searching algorithm with a time complexity of O(n).
It is a well-suited algorithm for small datasets. It can be used for both sorted and unsorted datasets.

Linear search - how does it work?

In Linear search, we iterate through the input dataset and compare each element with the element we are looking to find. When we find the match, we just end the iteration and return the index position of the element, or just the boolean value true, depending on what we are trying to accomplish.

Let's implement it

Below is a Java implementation of the Linear search algorithm

class LinearSearch {

  public int search(int[] arr, int element) {

    for (int i = 0; i < arr.length; i++) {
      if (arr[i] == element) {
        return i;
      }
    }

    return -1;
  }
}

So we start iterating from the start of the array (index 0) and we go through the input array until we find the matching element.

If the element is not found, we just return -1.

We can also use the Linear search to determine if an element is part of the dataset:

class LinearSearch {

  public boolean isPresent(int[] arr, int element) {

    for (int i = 0; i < arr.length; i++) {
      if (arr[i] == element) {
        return true;
      }
    }

    return false;
  }
}

In this case, we just return a boolean value to indicate if the value is present in the dataset or not.

Note: Instead of a traditional for loop, we can use an enhanced for loop or the forEach() method, that was introduced in Java 8.

Linear search - analysis

This algorithm has average and worst case complexity of O(n) and best case of O(1).

Best case O(1) - This algorithm can perform in a constant time if the value that we are looking for is on the position (index) of 0. In that case, we will end iteration after the first step.

Worst and average case O(n) - In the worst case, the element is at the last index of the array, so we need to traverse all until the end. In the average case, it is still O(n).

Space complexity is O(1) since we don't need any extra memory space.