Java Reference
In-Depth Information
takes a book to list them all. This is in fact how invalid credit card numbers are distrib-
uted to stores that do not have access to computers. If you are a clerk and are handed a
credit card, you must check to see if it is on the list and hence invalid. How would you
proceed? Open the topic to the middle and see if the number is there. If it is not and it
is smaller than the middle number, then work backward toward the beginning of the
book. If the number is larger than the middle number, you work your way toward the
end of the topic. This idea produces our first draft of an algorithm:
algorithm
first version
mid =
approximate midpoint between
0
and
finalIndex;
if
(key == a[mid])
return
mid;
else if
(key < a[mid])
search
a[0]
through
a[mid
−
1];
else if
(key > a[mid])
search
a[mid + 1]
through
a[finalIndex];
Since the searchings of the shorter lists are smaller versions of the very task we are
designing the algorithm to perform, this algorithm naturally lends itself to the use of
recursion. The smaller lists can be searched with recursive calls to the algorithm itself.
Our pseudocode is a bit too imprecise to be easily translated into Java code. The
problem has to do with the recursive calls. There are two recursive calls shown:
search
a[0]
through
a[mid
−
1];
and
search
a[mid + 1]
through
a[finalIndex];
To implement these recursive calls, we need two more parameters. A recursive call spec-
ifies that a subrange of the array is to be searched. In one case it is the elements indexed by
0
through
mid
−
1
. In the other case it is the elements indexed by
mid
+
1
through
final-
Index
. The two extra parameters will specify the first and last indices of the search, so we
will call them
first
and
last
. Using these parameters for the lowest and highest indices,
instead of
0
and
finalIndex
, we can express the pseudocode more precisely as follows:
more
parameters
algorithm
first
refinement
To search
a[first]
through
a[last]
do the following:
mid =
approximate midpoint between
first
and
last;
if
(key == a[mid])
return
mid;
else if
(key < a[mid])
return
the result of searching
a[first]
through
a[mid
−
1];
else if
(key > a[mid])
return
t
he result of searching
a[mid + 1]
through
a[last];
To search the entire array, the algorithm would be executed with
first
set equal to
0
and
last
set equal to
finalIndex
. The recursive calls will use other values for
first
and
last
. For example, the first recursive call would set
first
equal to
0
and
last
equal to the calculated value
mid
−
1
.
