Linear Search With Fewer Comparisons | Baeldung on Computer Science

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 $a$ with $n$ elements and a value $x$ . 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 $a$ 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 $O(n)$ brute-force algorithm:

Rendered by QuickLaTeX.com

If $x$ isn’t in $a$ , linear search performs $\boldsymbol{2n +1}$ comparisons: $2n$ are due to the loop’s termination test ( $i \leq n$ and $a[i] \neq x$ ) and 1 to the check $a[i] = x$ that comes after the loop.

4. Improving Linear Search

We can reduce the number of comparisons by appending $\boldsymbol{x}$ to $\boldsymbol{a}$ . That way, we modify the original array. If $n$ is the number of elements before appending $x$ , the appended element is $a[n+1]$ , and we make sure that $a[n+1] = x$ is true.

As a result, we don’t need to check if $\boldsymbol{i}$ is within the original array’s bounds ( $\boldsymbol{1 \leq i \leq n}$ ). If $x$ isn’t in $a[1:n]$ , $a[n+1] = x$ ensures we exit the loop after $i$ becomes greater than $n$ , so checking $i$ is unnecessary:

Rendered by QuickLaTeX.com

Therefore, if $i \leq n$ after exiting the loop, that means that we found $x$ in the input array ( $a[1:n]$ ), so we return $i$ . On the other hand, if $i = n + 1$ after exiting the loop, $x$ wasn’t found until $a[n+1]$ . The last element wasn’t originally in the array, so we return $false$ .

In total, the improved search does $\boldsymbol{n+2}$ comparisons in the worst case: we perform $n+1$ 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 $2n+1$ to $n+2$ , time complexity stays the same. Both versions of the algorithm are $O(n)$ .

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.

Full Archive

About Baeldung

1. Introduction

2. Number of Comparisons

3. Linear Search

4. Improving Linear Search

5. Conclusion