Searching - Data Structures and Abstractions with Java - page 451

18.11

One complication arises, however, when we write the recursive calls in the previous pseudocode.
Each call searches a subrange of the array. In the first case, it is the elements indexed by 0 through
mid - 1 . In the second case, it is the elements indexed by mid + 1 through n - 1 . Thus, we need two
extra parameters— first and last —to specify the first and last indices of the subrange of the array
that is to be searched. That is, we search a[first] through a[last] for desiredItem .
Using these parameters and making the recursive calls look more like Java, we can express the
pseudocode as follows:
Algorithm binarySearch(a, first, last, desiredItem)
mid = approximate midpoint between first and last
if (desiredItem equals a[mid])
return true
else if (desiredItem < a[mid])
return binarySearch(a, first, mid - 1, desiredItem)
else if (desiredItem > a[mid])
return binarySearch(a, mid + 1, last, desiredItem)
To search the entire array, we initially set first to 0 and last to n - 1 . Each recursive call will
then use some other values for first and last . For example, the recursive call that appears first
would set first to 0 and last to mid - 1 .
When you write any recursive algorithm, you should always check that the recursion is not
infinite. Let's check whether every possible invocation of the algorithm will lead to a base case.
Consider the three cases in the nested if statement in the previous pseudocode. In the first case, the
sought-after item is found in the array, so there is no recursive call, and the process terminates. In
each of the other two cases, a smaller portion of the array is searched by a recursive call. If the
sought-after item is in the array, the algorithm uses smaller and smaller portions of the array until it
finds the item. But what if the item is not anywhere in the array? Will the resulting series of recur-
sive calls eventually lead to a base case? Unfortunately not, but that is not hard to fix.

18.12

Note that in each recursive call, either the value of first is increased or the value of last is
decreased. If they ever pass each other and first actually becomes larger than last , we will have
run out of array elements to check. In that case, desiredItem is not in the array. If we add this test
to our pseudocode and refine the logic a bit, we get the following more complete algorithm:
Algorithm binarySearch(a, first, last, desiredItem)
mid = (first + last) / 2 // approximate midpoint
if (first > last)
return false
else if (desiredItem equals a[mid])
return true
else if (desiredItem < a[mid])
return binarySearch(a, first, mid - 1, desiredItem)
else // desiredItem > a[mid]
return binarySearch(a, mid + 1, last, desiredItem)
Figure 18-6 provides an example of a binary search.

Question 5 When the previous binary search algorithm searches the array in Figure 18-6
for 8 and for 16, how many comparisons to an array entry are necessary in each case?