Linear Search

If there is one algorithm that we all use almost on daily basis in our lives, it has to be Linear Search. It is one of the most intutive algorithms, that does not even require any special setup before we even start to perform the search operation.

Introduction

Linear Search is one of the most commonly used and intuitive search algorithms. It works similarly to how we learn to explore new things - browse through the set until you find what you are looking for.

We start by comparing the first item in the input with the key we are looking for. If we find a match, we return the index, or otherwise, we move ahead to the next element.

This will continue until we either run out of the elements in the input or find the element matching the key.

Let’s take a quick look at the sample java code:

public int linearSearch(int[] input, int key){
    for(int i = 0; i < input.length; i++){
      // if there is a match, return the current index 
      if(key == input[i]){
            return i;
       }
    }
    // if all the elements are checked
    // and we have not returned an index,
    // it means the key is not in the input array
    // return -1 to denote missing element
    return -1;
}

The runtime complexity of this algorithm is \(O(n)\) in the worst case which happens when:

1. Either the key matches the last element in the input.
2. Or is not present in the input altogether.

In both of these cases, the algorithm will iterate over all the elements before resulting in some value. The best case happens when the key matches the first element in the input.

An optimization trick can be used to improve the overall runtime by reducing the number of comparisons performed inside the for loop. The above-mentioned for loop has two comparison operations:

1. Check the index to ensure we do not exceed the input size bound.
2. Compare the current element with the key.

The trick is to add the key after the last element in the input (provided the data structure supports addition and is NOT fixed size like an array). This way, we do not have to worry about crossing the input bounds as we can now guarantee that we’ll find the key while traversing the input.

Once we find the key, we just need to perform one extra check to ensure that the selected index does not match the index on which we manually added the key. Although the overall complexity is still \(O(n)\), but we now have managed to remove an extra comparison in each iteration.