Binary Search Recursively

In Chapter 4 we wrote code for binary search that used a loop. Recall that binary search only works on an array that is sorted. Now let’s write a recursive version of binary search.

public static int binarySearch(char whatToFind, char[] theList){
   return binarySearch(whatToFind, theList, 0, theList.length - 1);
}

public static int binarySearch(char whatToFind, char[] theList, 
                               int low, int high){
   if (high < low){
      return -1;
   }
       
   int middle = (low + high) / 2;
   if (theList[middle] == whatToFind){
      return middle;
   }
   
   if (theList[middle] < whatToFind){
      return binarySearch(whatToFind, theList, middle + 1, high);
   }
   else{
      return binarySearch(whatToFind, theList, low, middle - 1);
   }
}

Practice Questions

1. Identify the base case(s) in the binary search recursive method.

2. Identify the recursive call(s) in the binary search recursive method.

3. Explain how the recursive call(s) move(s) toward base case(s) in the binary search recursive method.

4. Give the signature of the wrapper.

5. Draw a visualization of the call
   $$ binarySearch('k', {'a', 'd', 'h', 'k', 'm', 'p', 'r'}, 0, 6).

6. Draw a visualization of the call
   $$ binarySearch('e', {'a', 'd', 'h', 'k', 'm', 'p', 'r'}, 0, 6).

7. Draw a visualization of the call
   $$ binarySearch('r', {'a', 'd', 'h', 'k', 'm', 'p', 'r'}, 0, 6).

8. What is the maximum number of spots checked on a array of size 7? size 15? size $n$, where $n$ is one less than a power of 2?

9. Is binarySearch tail recursive? Why or why not?

To Solutions