The most common (not to be confused with optimal) and intiutive algorithm to search for an element in a set of elements.

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.

**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:

- Either the
`key`

matches the last element in the input. - 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:

- Check the index to ensure we do not exceed the input size bound.
- 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.

Be notified of new posts. Subscribe to the RSS feed.