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 .
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.