RECURSION - Introduction to Java Programming: Comprehensive Version - page 716

22 // Sort the remaining list[low+1 .. high]

23 sort(list, low + 1 , high);

recursive call

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.

18.5.2 Recursive Binary Search
Binary search was introduced in Section 7.10.2. For binary search to work, the elements in the
array must be in 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 18.6 gives a
clear, simple solution for the binary search problem using recursion.

L ISTING 18.6

Recursive Binary Search Method
1 public class RecursiveBinarySearch {
2

public static int recursiveBinarySearch( int [] list, int key) {

3 int low = 0 ;

4 int high = list.length - 1 ;

5 return recursiveBinarySearch(list, key, low, high);

6 }
7
8 private static int recursiveBinarySearch( int [] list, int key,

helper method

9 int low, int high) {

10 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])

15 return recursiveBinarySearch(list, key, low, mid - 1 ); recursive call

16 else if (key == list[mid])

17 return mid;

base case

18 else

19 return recursiveBinarySearch(list, key, mid + 1 , high); recursive call

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.