Linear Search With Fewer Comparisons

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:

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: