Contents

1 About this module

• Prerequisites: 0054
• Objectives: This module improves the linear search algorithm for sorted arrays. It also introduces binary search, a very efficient search algorithm for sorted arrays.

2 Sorted arrays

The linear search algorithm in module 0054 is the only kind of search algorithm that works on unsorted arrays. In the worst case, all elements in the array must be examined to confirm that a value is not in the array.

With sorted arrays, however, we can make some improvements.

Assume that array $a$ is sorted, and assume $n=\left|a\right|$ is the number of elements in the array. Furthermore, let us assume that the array is sorted in a non-decreasing order. This implies that we can have duplicate values in the array. The mathematical way to say an array is sorted in a non-decreasing order is as follows:

$a\left[i\right]\le a\left[i+1\right]$ for $i$ from 0 to $n-2$. We can also spell this out as $a\left[0\right]\le a\left[1\right]\le a\left[2\right]\dots a\left[n-1\right]$.

3 Linear search

We can improve our linear search algorithm to work more efficiently. The original algorithm is described as algorithm 1.

Note that if we find that $v<a\left[i\right]$, then we already know that $v<a\left[i\right]\le a\left[i+1\right]\le a\left[i+2\right]\dots a\left[n-1\right]$ because the array is sorted. This also means that $v\ne a\left[i+1\right]$, $v\ne a\left[i+2\right]$, all the way up to $v\ne a\left[n-1\right]$.

This property of a sorted array means that we can exit the loop earlier when we discover that $v<a\left[i\right]$. This is great new! On the other hand, we need to modify the conditional statement because now we can exit with $i<\left|a\right|$ and still conclude that value $v$ is not anywhere in the array. The condition that confirms that value $v$ is not in the array should be $\left(i=\left|a\right|\right)\vee \left(a\left[i\right]\ne v\right)$.

As a result, the algorithm is modified as in algorithm 2.

With this modification, the number of elements to examine is variable when the value $v$ is not in the array. Nonetheless, in the worst case, when $v>a\left[n-1\right]$, we still need to examine all $n$ items in the array.

4 Binary search

4.1 Concept

Binary search works only if an array is sorted. The basic idea is to compare the value to find with an element in the middle of the array. Depending on the outcome, we can throw away one half of the candidates, or confirm the value does exist.

Let us assume that we compare $v$ with $a\left[m\right]$, the first candidate has an index of $b$, and the last candidate has an index of $e$. Then, there are three possible outcomes:

• $v=a\left[m\right]$: the search is over! We just confirmed that value $v$ can be found in the array.
• $v<a\left[m\right]$: we can throw away $a\left[m\right]$, $a\left[m+1\right]$,... $a\left[e\right]$.
• $v>a\left[m\right]$: we can throw away $a\left[b\right]$, $a\left[b+1\right]$,... $a\left[m\right]$.

If we pick $m$ to be half way between $b$ and $e$, then we can throw away at least one half of the candidates after one comparison.

4.2 Algorithm

The binary search algorithm is described in algorithm 3. This algorithm assumes that $a$ is an array with at least one item, and $v$ is the value that we are searching for.

Let us dissect this algorithm.

• Lines 1 and 2 initialize variables $b$ and $e$, respectively. $b$ is the index of the first element that can still contain value $v$. It is initialized to 0 because we need to consider all elements initially. For the same reason, $e$ is initialized to $\left|a\right|-1$ because that is the index of the last element in the entire array.
• Everything between line 3 and line 12 is the logic of binary search.
• Line 4 computes the value of $m$ so it is half-way between $b$ and $e$. The symbol $\lfloor x\rfloor$ is called the “floor” of $x$. The floor of $x$ is the largest integer that is less than or equal to $x$. In this context, we are simply truncating any fractional value.
• Line 5 checks to see if we can remove the first half of the candidates. If $a\left[m\right]<v$, then we know that $a\left[b\right]\le a\left[b+1\right]\le a\left[b+2\right]\dots a\left[m\right]<v$, and so we can eliminate all those elements as candidates.
• Line 6: Once we know that we can eliminate the first half of the candidates, we can do so by changing $b$. Note that we do not change to $b$ to $m$ because $a\left[m\right]\ne v$. Instead, we move $b$ to $m+1$. This subtle point makes all the differences in terms of terminating the loop.
• Lines 8 and 9 are the counterparts of lines 5 and 6. Instead of getting rid of the first half, these lines checks to see if we can eliminate the self half.
• Line 12 specifies when we can get out of the loop. There are two reasons. First, when $b>e$, we have no candidates left. Note that when $b=e$, it means that there is one more element to be considered. Second, when $a\left[m\right]=v$, there is nothing to check anymore, because we have just found an element of value $v$.
• Line 13 checks to see if value $v$ is found in the array or not. If $b>e$, it means that we exited the loop because we ran out of candidates. Therefore, we can then confirm that value $v$ does not exist in $a$.

4.3 Now, that’s efficient!

The binary search algorithm is very efficient because each comparison eliminates at least one half of the remaining candidates. This means that if we start off with 511 candidates, we’ll end up with 255 after one comparison, 127 after two comparisons, 63 after three comparisons, and etc. It’ll take 9 comparisons that confirm a value $v$ is not in an array of 511 elements.

Let $n=\left|a\right|$, and $q$ be the number of comparisons needed to confirm $v$ is not in $a$. Then $q=\lceil log\left(n\right)∕log\left(2\right)\rceil$. The symbol $\lceil x\rceil$ is the ceiling of $x$, which is the smallest integer that is larger than or equal to $x$.

Using this formula, to look up a name in a phonebook with 6 billion entries will only take up to 33 comparisons!