Java Reference
In-Depth Information
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];
}