27.3. Search in Sorted Arrays¶

For large collections of records that are searched repeatedly, sequential search is unacceptably slow. One way to reduce search time is to preprocess the records by sorting them. Given a sorted array, an obvious improvement over simple linear search is to test if the current element in L is greater than $K$. If it is, then we know that $K$ cannot appear later in the array, and we can quit the search early. But this still does not improve the worst-case cost of the algorithm.

We can also observe that if we look first at position 1 in sorted array L and find that K is bigger, then we rule out position 0 as well as position 1. Because more is often better, what if we look at position 2 in L and find that $K$ is bigger yet? This rules out positions 0, 1, and 2 with one comparison. What if we carry this to the extreme and look first at the last position in L and find that $K$ is bigger? Then we know in one comparison that $K$ is not in L. This is useful to know, but what is wrong with the conclusion that we should always start by looking at the last position? The problem is that, while we learn a lot sometimes (in one comparison we might learn that $K$ is not in the list), usually we learn only a little bit (that the last element is not $K$).

The question then becomes: What is the right amount to jump? This leads us to an algorithm known as Jump Search. For some value $j$, we check every $j$ 'th element in L, that is, we check elements $\mathbf{L}[j]$, $\mathbf{L}[2j]$, and so on. So long as $K$ is greater than the values we are checking, we continue on. But when we reach a value in L greater than $K$, we do a linear search on the piece of length $j-1$ that we know brackets $K$ if it is in the list.

If we define $m$ such that $mj \leq n < (m+1)j$, then the total cost of this algorithm is at most $m + j - 1$ 3-way comparisons. (They are 3-way because at each comparison of $K$ with some $\mathbf{L}[i]$ we need to know if $K$ is less than, equal to, or greater than $\mathbf{L}[i]$.) Therefore, the cost to run the algorithm on $n$ items with a jump of size $j$ is

\[\mathbf{T}(n, j) = m + j - 1 = \left\lfloor \frac{n}{j} \right\rfloor + j - 1.\]

What is the best value that we can pick for $j$? We want to minimize the cost:

\[\min_{1 \leq j \leq n} \left\{\left\lfloor\frac{n}{j}\right\rfloor + j - 1\right\}\]

Take the derivative and solve for $f'(j) = 0$ to find the minimum, which is $j = \sqrt{n}$. In this case, the worst case cost will be roughly $2\sqrt{n}$.

This example invokes a basic principle of algorithm design. We want to balance the work done while selecting a sublist with the work done while searching a sublist. In general, it is a good strategy to make subproblems of equal effort. This is an example of a divide and conquer algorithm.

What if we extend this idea to three levels? We would first make jumps of some size $j$ to find a sublist of size $j-1$ whose end values bracket value $K$. We would then work through this sublist by making jumps of some smaller size, say $j_1$. Finally, once we find a bracketed sublist of size $j_1 - 1$, we would do sequential search to complete the process.

This probably sounds convoluted to do two levels of jumping to be followed by a sequential search. While it might make sense to do a two-level algorithm (that is, jump search jumps to find a sublist and then does sequential search on the sublist), it almost never seems to make sense to do a three-level algorithm. Instead, when we go beyond two levels, we nearly always generalize by using recursion. This leads us to the most commonly used search algorithm for sorted arrays, the binary search.

If we know nothing about the distribution of key values, then binary search is the best algorithm available for searching a sorted array. However, sometimes we do know something about the expected key distribution. Consider the typical behavior of a person looking up a word in a large dictionary. Most people certainly do not use sequential search! Typically, people use a modified form of binary search, at least until they get close to the word that they are looking for. The search generally does not start at the middle of the dictionary. A person looking for a word starting with 'S' generally assumes that entries beginning with 'S' start about three quarters of the way through the dictionary. Thus, he or she will first open the dictionary about three quarters of the way through and then make a decision based on what is found as to where to look next. In other words, people typically use some knowledge about the expected distribution of key values to "compute" where to look next. This form of "computed" binary search is called a dictionary search or interpolation search. In a dictionary search, we search L at a position $p$ that is appropriate to the value of $K$ as follows.

\[p = \frac{K - \mathbf{L}[1]}{\mathbf{L}[n] - \mathbf{L}[1]}\]

This equation is computing the position of $K$ as a fraction of the distance between the smallest and largest key values. This will next be translated into that position which is the same fraction of the way through the array, and this position is checked first. As with binary search, the value of the key found eliminates all records either above or below that position. The actual value of the key found can then be used to compute a new position within the remaining range of the array. The next check is made based on the new computation. This proceeds until either the desired record is found, or the array is narrowed until no records are left.

A variation on dictionary search is known as $Quadratic Binary Search$ (QBS), and we will analyze this in detail because its analysis is easier than that of the general dictionary search. QBS will first compute (p) and then examine $\mathbf{L}[\lceil pn\rceil]$. If $K < \mathbf{L}[\lceil pn\rceil]$ then QBS will sequentially probe to the left by steps of size $\sqrt{n}$, that is, we step through

\[\mathbf{L}[\lceil pn - i\sqrt{n}\rceil], i = 1, 2, 3, ...\]

until we reach a value less than or equal to $K$. Similarly for $K > \mathbf{L}[\lceil pn\rceil]$ we will step to the right by $\sqrt{n}$ until we reach a value in L that is greater than $K$. We are now within $\sqrt{n}$ positions of $K$. Assume (for now) that it takes a constant number of comparisons to bracket $K$ within a sublist of size $\sqrt{n}$. We then take this sublist and repeat the process recursively. That is, at the next level we compute an interpolation to start somewhere in the subarray. We then step to the left or right (as appropriate) by steps of size $\sqrt{\sqrt{n}}$.

What is the cost for QBS? Note that $\sqrt{c^n} =c^{n/2}$, and we will be repeatedly taking square roots of the current sublist size until we find the item that we are looking for. Because $n = 2^{\log n}$ and we can cut $\log n$ in half only $\log \log n$ times, the cost is $\Theta(\log \log n)$ if the number of probes on jump search is constant.

Say that the number of comparisons needed is $i$, in which case the cost is $i$ (since we have to do $i$ comparisons). If $\mathbf{P}_i$ is the probability of needing exactly $i$ probes, then

\[\begin{split}\sum_{i=1}^{\sqrt{n}} i \mathbf{P}(\mbox{need exactly $i$ probes})\\ = 1 \mathbf{P}_1 + 2 \mathbf{P}_2 + 3 \mathbf{P}_3 + \cdots + \sqrt{n} \mathbf{P}_{\sqrt{n}}\end{split}\]

We now show that this is the same as

\[\sum_{i=1}^{\sqrt{n}} \mathbf{P}(\mbox{need at least $i$ probes})\]

\[\begin{split}&=& 1 + (1-\mathbf{P}_1) + (1-\mathbf{P}_1-\mathbf{P}_2) + \cdots + \mathbf{P}_{\sqrt{n}}\\ &=& (\mathbf{P}_1 + ... + \mathbf{P}_{\sqrt{n}}) + (\mathbf{P}_2 + ... + \mathbf{P}_{\sqrt{n}}) +\\ && \qquad (\mathbf{P}_3 + ... + \mathbf{P}_{\sqrt{n}}) + \cdots\\ &=& 1 \mathbf{P}_1 + 2 \mathbf{P}_2 + 3 \mathbf{P}_3 + \cdots + \sqrt{n} \mathbf{P}_{\sqrt{n}}\end{split}\]

We require at least two probes to set the bounds, so the cost is

\[2 + \sum_{i=3}^{\sqrt{n}} \mathbf{P}(\mbox{need at least $i$ probes}).\]

We now make take advantage of a useful fact known as Chebyshev's Inequality. Chebyshev's inequality states that $\mathbf{P}(\mbox{need exactly}\ i\ \mbox{probes})$, or $\mathbf{P}_i$, is

\[\mathbf{P}_i \leq \frac{p(1 - p)n}{(i - 2)^2 n} \leq \frac{1}{4(i-2)^2}\]

because $p(1-p) \leq 1/4$ for any probability $p$. This assumes uniformly distributed data. Thus, the expected number of probes is

\[\begin{split}2 + \sum_{i=3}^{\sqrt{n}} \frac{1}{4(i-2)^2} < 2 + \frac{1}{4}\sum_{i=1}^\infty \frac{1}{i^2} = 2 + \frac{1}{4}\frac{\pi}{6} \approx 2.4112\end{split}\]

Is QBS better than binary search? Theoretically yes, because $O(\log \log n)$ grows slower than $O(\log n)$. However, we have a situation here which illustrates the limits to the model of asymptotic complexity in some practical situations. Yes, $c_1 \log n$ does grow faster than $c_2 \log \log n$. In fact, it is exponentially faster! But even so, for practical input sizes, the absolute cost difference is fairly small. Thus, the constant factors might play a role. First we compare $\log \log n$ to $\log n$.

\[\begin{split}\begin{array}{llll} &&&{\rm Factor}\\ n &\log n&\log \log n&{\rm Difference}\\ \hline 16 &4 &2 &2\\ 256&8 &3 &2.7\\ 2^{16}&16 &4 &4\\ 2^{32}&32 &5 &6.4\\ \end{array}\end{split}\]

It is not always practical to reduce an algorithm's growth rate. There is a "practicality window" for every problem, in that we have a practical limit to how big an input we wish to solve for. If our problem size never grows too big, it might not matter if we can reduce the cost by an extra log factor, because the constant factors in the two algorithms might differ by more than the log of the log of the input size.

For our two algorithms, let us look further and check the actual number of comparisons used. For binary search, we need about $\log n-1$ total comparisons. Quadratic binary search requires about $2.4 \log \log n$ comparisons. If we incorporate this observation into our table, we get a different picture about the relative differences.

\[\begin{split}\begin{array}{llll} &&&{\rm Factor}\\ n &\log n -1&2.4 \log \log n&{\rm Difference}\\ \hline 16&3&4.8&{\rm worse}\\ 256&7&7.2&\approx {\rm same}\\ 64K&15&9.6&1.6\\ 2^{32}&31&12&2.6 \end{array}\end{split}\]

But we still are not done. This is only a count of raw comparisons. Binary search is inherently much simpler than QBS, because binary search only needs to calculate the midpoint position of the array before each comparison, while quadratic binary search must calculate an interpolation point which is more expensive. So the constant factors for QBS are even higher.

Not only are the constant factors worse on average, but QBS is far more dependent than binary search on good data distribution to perform well. For example, imagine that you are searching a telephone directory for the name "Young". Normally you would look near the back of the book. If you found a name beginning with 'Z', you might look just a little ways toward the front. If the next name you find also begins with 'Z' you would look a little further toward the front. If this particular telephone directory were unusual in that half of the entries begin with 'Z', then you would need to move toward the front many times, each time eliminating relatively few records from the search. In the extreme, the performance of interpolation search might not be much better than sequential search if the distribution of key values is badly calculated.

While it turns out that QBS is not a practical algorithm, this is not a typical situation. Fortunately, algorithm growth rates are usually well behaved, so that asymptotic algorithm analysis nearly always gives us a practical indication for which of two algorithms is better.

Chapter 27 Searching

27.3. Search in Sorted Arrays¶