Java Reference
In-Depth Information
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 topic. 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];
Because 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];
more
parameters
To implement these recursive calls, we need two more parameters. A recursive call
specifies 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
finalIndex
. 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:
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
the 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
.
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
stopping case
