Java Reference
In-Depth Information
As with any recursive algorithm, we must ensure that our algorithm ends rather
than producing infinite recursion. If the sought-after number is found on the list, then
there 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
actu-
ally 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 only wanted 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
.
stopping case
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
t
he result of searching
a[mid + 1]
through
a[last];
}