Recursion - Absolute Java - page 670

is no recursive call and the process terminates, but we need some way to detect when
the number is not on the list. On each recursive call, 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 , then we will know that there are no more indices left to check and
that the number key is not in the array. If we add this test to our pseudocode, we
obtain a complete solution, as shown in Display 11.5 .
Now we can routinely translate the pseudocode into Java code. The result is shown
in Display 11.6 . The method search is an implementation of the recursive algorithm
given in Display 11.5. A diagram of how the method performs on a sample array is
given in Display 11.7 . Display 11.8 illustrates how the method search is used.
Notice that the method search solves a more general problem than the original
task. Our goal was to design a method to search an entire array. Yet the method will
let us search any interval of the array by specifying the indices first and last . This
is common when designing recursive methods. Frequently, it is necessary to solve a
more general problem in order to be able to express the recursive algorithm. In this
case, we want only the answer in the case where first and last are set equal to 0
and finalIndex . However, the recursive calls will set them to values other than 0 and
finalIndex .

algorithm
final version

Display 11.5 Pseudocode for Binary Search ★

A LGORITHM TO SEARCH a[first] THROUGH a[last]
/**
Precondition:
a[first] <= a[first + 1] < = a[first + 2] <= … <= a[last]
*/

T O LOCATE THE VALUE KEY
if (first > last) //A stopping case
return -1;
else
{
mid = approximate midpoint between first and last;
if (key == a[mid]) //A stopping case
return mid;
else if key < a[mid] //A case with recursion
return the result of searching a[first] through a[mid - 1];

else if key > a[mid] // A case with recursion
return the result of searching a[mid + 1] through a[last];
}