If you have a few years of experience in Computer Science or research, and you’re interested in sharing that experience with the community, have a look at our **Contribution Guidelines**.

# Linear Search With Fewer Comparisons

Last modified: November 23, 2022

## 1. Introduction

In this tutorial, we’ll show how to minimize the number of comparisons in linear search.

## 2. Number of Comparisons

Let’s say we have an array with elements and a value . Our goal is to check if the value is in the array and, in doing so, make the least possible number of comparisons. Here, we count all comparisons, even those involving auxiliary variables in loops.

Although minimizing the number of comparisons may not be very useful in everyday applications, there are use cases where each optimization counts. For instance, **code running in embedded systems with restricted memory needs to use resources optimally,** so it makes sense to try low-level optimization hacks in such scenarios.

We assume that isn’t sorted and that indexing starts from 1.

## 3. Linear Search

Usually, we run the linear search to solve this problem. It’s an brute-force algorithm:

If isn’t in , **linear search performs comparisons**: are due to the loop’s termination test ( *and* ) and 1 to the check that comes after the loop.

## 4. Improving Linear Search

**We can reduce the number of comparisons by appending to .** That way, we modify the original array. If is the number of elements before appending , the appended element is , and we make sure that is true.

As a result, **we don’t need to check if is within the original array’s bounds ().** If isn’t in , ensures we exit the loop after becomes greater than , so checking is unnecessary:

Therefore, if after exiting the loop, that means that we found in the input array (), so we return . On the other hand, if after exiting the loop, wasn’t found until . The last element wasn’t originally in the array, so we return .

In total, **the improved search does comparisons in the worst case**: we perform by checking the loop’s termination condition, and 1 is done in the final test after the loop.

Although we reduce the number of comparisons from to , **time complexity**** stays the same.** Both versions of the algorithm are .

## 5. Conclusion

In this article, we showed an improved version of linear search. By appending the search value to an unsorted array, we ensure the search will find it in the end, so it isn’t necessary to check if array indices are out of bounds.