## 2.1 Binary Search We showed an iterative version of Binary Search ([Algorithm 1.5](LiB0009.html#38)) in [Section 1.2](LiB0016.html#154). Here we present a recursive version because recursion illustrates the top-down approach used by divide-and-conquer. Stated in divide-and-conquer terminology, Binary Search locates a key *x* in a sorted (nondecreasing order) array by first comparing *x* with the middle item of the array. If they are equal, the algorithm is done. If not, the array is divided into two subarrays, one containing all the items to the left of the middle item and the other containing all the items to the right. If *x* is smaller than the middle item, this procedure is then applied to the left subarray. Otherwise, it is applied to the right subarray. That is, *x* is compared with the middle item of the appropriate subarray. If they are equal, the algorithm is done. If not, the subarray is divided in two. This procedure is repeated until *x* is found or it is determined that *x* is not in the array. The steps of Binary Search can be summarized as follows. If *x* equals the middle item, quit. Otherwise: 1. *Divide* the array into two subarrays about half as large. If *x* is smaller than the middle item, choose the left subarray. If *x* is larger than the middle item, choose the right subarray. 2. *Conquer* (solve) the subarray by determining whether *x* is in that subarray. Unless the subarray is sufficiently small, use recursion to do this. 3. *Obtain* the solution to the array from the solution to the subarray. Binary Search is the simplest kind of divide-and-conquer algorithm because the instance is broken down into only one smaller instance, so there is no combination of outputs. The solution to the original instance is simply the solution to the smaller instance. The following example illustrates Binary Search. Example 2.1****Suppose *x* = 18 and we have the following array:  1. Divide the array: Because *x* <25, we need to search 10 聽12 聽13 聽14 聽18 聽20. 2. Conquer the subarray by determining whether *x* is in the subarray. This is accomplished by recursively dividing the subarray. The solution is: Yes, *x* is in the subarray. 3. Obtain the solution to the array from the solution to the subarray: Yes, *x* is in the array. **** In Step 2 we simply assumed that the solution to the subarray was available. We did not discuss all the details involved in obtaining the solution because we wanted to show the solution at a problem-solving level. When developing a recursive algorithm for a problem, we need to - Develop a way to obtain the solution to an instance from the solution to one or more smaller instances. - Determine the terminal condition(s) that the smaller instance(s) is (are) approaching. - Determine the solution in the case of the terminal condition(s). We need not be concerned with the details of how the solution is obtained (in the case of a computer, by means of stack manipulations). Indeed, worrying about these details can sometimes hinder one's development of a complex recursive algorithm. For the sake of concreteness, [Figure 2.1](#ch02fig01) shows the steps done by a human when searching with Binary Search. [](fig2-1_0.jpg) Figure 2.1: The steps done by a human when searching with Binary Search. (*Note:x* = 18.) A recursive version of Binary Search now follows. Algorithm 2.1: Binary Search (Recursive)****Problem: Determine whether *x* is in the sorted array *S* of size *n.* Inputs: positive integer *n*, sorted (nondecreasing order) array of keys *S* indexed from 1 to *n*, a key *x.* Outputs: *location*, the location of *x* in *S* (0 if *x* is not in *S*). ``` index location (index low, index high) { index mid; if (low > high) return 0; else { mid = [(low + high)/2]; if (x == S[mid]) return mid else if (x == S[mid]) return location(low, mid - 1); else return location(mid + 1, high); } } ``` **** Notice that *n, S*, and *x* are not parameters to function *location.* Because they remain unchanged in each recursive call, there is no need to make them parameters. In this text only the variables, whose values can change in the recursive calls, are made parameters to recursive routines. There are two reasons for doing this. First, it makes the expression of recursive routines less cluttered. Second, in an actual implementation of a recursive routine, a new copy of any variable passed to the routine is made in each recursive call. If a variable's value does not change, the copy is unnecessary. This waste could be costly if the variable is an array. One way to circumvent this problem would be to pass the variable by address. Indeed, if the implementation language is C++, an array is automatically passed by address, and using the reserved word **const** guarantees the array cannot be modified. However, including all of this in our pseudocode expression of recursive algorithms again serves to clutter them and possibly diminish their clarity. Each of the recursive algorithms could be implemented in a number of ways, depending on the language used for the implementation. For example, one possible way to implement them in C++ would be pass all the parameters to the recursive routine; another would be to use classes; and yet another would be to globally define the parameters that do not change in the recursive calls. We will illustrate how to implement the last one since this is the alternative consistent with our expression of the algorithms. If we did define *S* and *x* globally and *n* was the number of items in *S*, our top-level call to function *location* in [Algorithm 2.1](#ch02ex02) would be as follows: *locationout* = *location*(1, *n*); Because the recursive version of Binary Search employs ***tail-recursion*** (that is, no operations are done after the recursive call), it is straightforward to produce an iterative version, as was done in [Section 1.2](LiB0016.html#154). As previously discussed, we have written a recursive version because recursion clearly illustrates the divide-and-conquer process of dividing an instance into smaller instances. However, it is advantageous in languages such as C++ to replace tail-recursion by iteration. Most importantly, a substantial amount of memory can be saved by eliminating the stack developed in the recursive calls. Recall that when a routine calls another routine it is necessary to save the first routine's pending results by pushing them onto the stack of activation records. If the second routine calls another routine, the second routine's pending results must also be pushed onto the stack, and so on. When control is returned to a calling routine, its activation record is popped from the stack and the computation of the pending results is completed. In the case of a recursive routine, the number of activation records pushed onto the stack is determined by the depth reached in the recursive calls. For Binary Search, the stack reaches a depth that in the worst case is about lg *n* + 1. Another reason for replacing tail-recursion by iteration is that the iterative algorithm will execute faster (but only by a constant multiplicative factor) than the recursive version because no stack needs to be maintained. Because most modern LISP dialects compile tail-recursion to iterative code, there is no reason to replace tail-recursion by iteration in these dialects. Binary Search does not have an every-case time complexity. We will do a worst-case analysis. We already did this informally in [Section 1.2](LiB0016.html#154). Here we do the analysis more rigorously. Although the analysis refers to [Algorithm 2.1](#ch02ex02), it pertains to [Algorithm 1.5](LiB0009.html#38) as well. If you are not familiar with techniques for solving recurrence equations, you should study [Appendix B](LiB0102.html#1369) before proceeding. ****Analysis of [Algorithm 2.1](#ch02ex02) Worst-Case Time Complexity (Binary Search, Recursive)In an algorithm that searches an array, the most costly operation is usually the comparison of the search item with an array item. Thus, we have the following: Basic operation: the comparison of *x* with *S\[mid\].* Input size: *n*, the number of items in the array. We first analyze the case in which *n* is a power of 2. There are two comparisons of *x* with *S\[mid\]* in any call to function *location* in which *x* does not equal *S\[mid\].* However, as discussed in our informal analysis of Binary Search in [Section 1.2](LiB0016.html#154), we can assume that there is only one comparison, because this would be the case in an efficient assembler language implementation. Recall from [Section 1.3](LiB0017.html#172) that we ordinarily assume that the basic operation is implemented as efficiently as possible. As discussed in [Section 1.2](LiB0016.html#154), one way the worst case can occur is when *x* is larger than all array items. If *n* is a power of 2 and *x* is larger than all the array items, each recursive call reduces the instance to one exactly half as big. For example, if *n* = 16, then *mid* = \[(1 + 16)/2\] = 8. Because *x* is larger than all the array items, the top eight items are the input to the first recursive call. Similarly, the top four items are the input to the second recursive call, and so on. We have the following recurrence:  If *n* = 1 and *x* is larger than the single array item, there is a comparison of *x* with that item followed by a recursive call with *low* > *high.* At this point the terminal condition is true, which means that there are no more comparisons. Therefore, *W*(1) is 1. We have established the recurrence  This recurrence is solved in Example B.1 in [Appendix B](LiB0102.html#1369). The solution is  If *n* is not restricted to being a power of 2, then  where \[*y*\] means the greatest integer less than or equal to *y.* We show how to establish this result in the exercises. ****