Java Reference
In-Depth Information
Display 11.6
Recursive Method for Binary Search
★
1
public
class
BinarySearch
2{
3
/**
−
4
Searches the array a for key. If key is not in the array segment, then
1 is
5
returned. Otherwise returns an index in the segment such that key == a[index].
6
Precondition: a[first] <= a[first + 1]<= ... <= a[last]
7
*/
8
public static int
search(
int
[] a,
int
first,
int
last,
int
key)
9
{
10
int
result = 0;
//to keep the compiler happy.
11
if
(first > last)
12
result =
−
1;
13
else
14
{
15
int
mid = (first + last)/2;
16
if
(key == a[mid])
17
result = mid;
18
else if
(key < a[mid])
19
result = search(a, first, mid
−
1, key);
20
else if
(key > a[mid])
21
result = search(a, mid + 1, last, key);
22
}
23
return
result;
24
}
25
}
In the subsection entitled “Tracing a Recursive Call,” we gave three criteria that you
should check to ensure that a recursive
void
method definition is correct. Let's check
these three things for the method
search
given in Display 11.6:
1.
There is no infinite recursion:
On each recursive call the value of
first
is
increased or the value of
last
is decreased. If the chain of recursive calls does not
end in some other way, then eventually the method will be called with
first
larger
than
last
, and that is a stopping case.
2.
Each stopping case performs the correct action for that case:
There are two stop-
ping cases, when
first
>
last
and when
key
==
a[mid]
. Let's consider each case.
If
first
>
last
, there are no array elements between
a[first]
and
a[last]
and so
key
is not in this segment of the array. (Nothing is in this segment of the array!) So,
if
first
>
last
, the method
search
correctly returns
−
1
, indicating that
key
is not
in the specified range of the array.
If
key
==
a[mid]
, the algorithm correctly sets
location
equal to
mid
. Thus, both
stopping cases are correct.
