CPSC 170 Post Lab 5: Recursive Binary Search

As we also discussed in class, binary search is an inherently recursive algorithm. The pseudocode that we wrote for a binary search method that looks for item target between indices lo and hi in array a looked something like this:

boolean binarySearch(Object target, Object[] a, int lo, int hi)
 
   if lo and hi have not crossed
       compute index mid
       if target = a[mid]
          return true
       else if target < a[mid]
          do binary search between lo and mid-1 and return this value
       else //target > a[mid]
          do binary search between mid+1 and hi and return this value
   else
       return false;

Assignment

1. Add a recursive binary search method to your Searching class. Its parameters and return value should be the same as in the pseudocode method above.

2. Modify your driver to give a binary search option. Test your method thoroughly. Remember that the array has to be sorted first.

3. Notice that in your driver you had to pass two extra parameters (lo and hi) to the recursive binary search method that were not necessary for the iterative binary search. Now overload your recursive binary search method with a version that has exactly the same interface (return type and parameters) as the iterative binary search method, and have this new method make the initial call to your recursive binary search method. Now have the driver call this new method instead. So instead of this:

   recBinarySearch(a, target, 0, a.length-1)
   

   the call in your driver will now look like this:

   recBinarySearch(a,target)
   

   Note that all the work is still being done in your original (4-parameter) recBinarySearch method; the new (2-parameter) method just calls it. It is often useful to "set up" a call to a recursive method in this way so that the extra parameters needed by the recursive method are not visible from the outside.