Java Reference
In-Depth Information
22
// Sort the remaining list[low+1 .. high]
sort(list, low +
1
, high);
recursive call
23
24 }
25 }
26 }
Two overloaded
sort
methods are defined. The first method,
sort(double[] list)
, sorts
an array in
list[0..list.length - 1]
and the second method,
sort(double[]
list, int low, int high)
, sorts an array in
list[low..high]
. The second method
can be invoked recursively to sort an ever-shrinking subarray.
20.5.2 Recursive Binary Search
Binary search was introduced in Section 6.10.2. For binary search to work, the elements in
the array must be in an increasing order. The binary search first compares the key with the
element in the middle of the array. Consider the following three cases:
VideoNote
Binary search
Case 1: If the key is less than the middle element, recursively search for the key in
the first half of the array.
■
Case 2: If the key is equal to the middle element, the search ends with a match.
■
Case 3: If the key is greater than the middle element, recursively search for the key
in the second half of the array.
■
Case 1 and Case 3 reduce the search to a smaller list. Case 2 is a base case when there is a
match. Another base case is that the search is exhausted without a match. Listing 20.6 gives a
clear, simple solution for the binary search problem using recursion.
L
ISTING
20.6
Recursive Binary Search Method
1
public class
RecursiveBinarySearch {
2
3
public static int
recursiveBinarySearch(
int
[] list,
int
key) {
int
low =
0
;
4
int
high = list.length -
1
;
5
return
recursiveBinarySearch(list, key, low, high);
6 }
7
8
9
10
private static int
recursiveBinarySearch(
int
[] list,
int
key,
helper method
int
low,
int
high) {
if
(low > high)
// The list has been exhausted without a match
base case
11
return
-low -
1
;
12
13
int
mid = (low + high) /
2
;
14
if
(key < list[mid])
return
recursiveBinarySearch(list, key, low, mid -
1
);
recursive call
15
16
else if
(key == list[mid])
base case
17
return
mid;
18
else
return
recursiveBinarySearch(list, key, mid +
1
, high);
recursive call
19
20 }
21 }
The first method finds a key in the whole list. The second method finds a key in the list with
index from
low
to
high
.
The first
binarySearch
method passes the initial array with
low = 0
and
high =
list.length - 1
to the second
binarySearch
method. The second method is invoked
recursively to find the key in an ever-shrinking subarray.
