/**
 * Recursive version of binary search algorithm
 * @author Suzanne Balik, 10 Nov 2001
 *
 * PRE: Array is in sorted (non-descending) order
 */
public class RecursiveBinarySearch {

  public static boolean search(int[] array, int toBeFound) {
  
    return searchHelper(array, toBeFound, 0, array.length - 1);
    
  }
   
   private static boolean searchHelper(int[] array, int toBeFound, 
                                       int first, int last){
   
     if (first > last)
       
       return false;
     
     int mid = (last - first)/2 + first;
     
     if (toBeFound == array[mid])
     
       return true;
       
     if (toBeFound < array[mid])
     
       return searchHelper(array, toBeFound, first, mid - 1);
       
     return searchHelper(array, toBeFound, mid + 1, last);
   }  
   
   public static void main(String[] args) {
   
     //Test with an array with an odd number of elements
     int[] numbers = {2, 3, 3, 6, 8, 9, 10};
     
     final int MAX = 20;
     
     for (int i = -5; i < MAX; i++)
     
       System.out.println(i + " is in array?: " + 
                          search(numbers, i));
     
     //Test with an array with an even number of elements  
     int[] values = {2, 3, 3, 6, 8, 10};
     
     for (int i = -5; i < MAX; i++)
     
       System.out.println(i + " is in array?: " + 
                          search(values, i));  
      
     //Test with an array with one element 
     int[] oneValue = {6};
     
     for (int i = -5; i < MAX; i++)
     
       System.out.println(i + " is in array?: " + 
                          search(oneValue, i));   
     
     //Test with an array with no elements 
     int[] noValues = {};
     
     for (int i = -5; i < MAX; i++)
     
       System.out.println(i + " is in array?: " + 
                          search(noValues, i));
       
  }
}