/**
 * CS151 Fall 2007 Lecuture code for recursive version of binary search.
 * 
 * @author Scott Russell 
 * @version 12/07/2007
 */
public class Search
{
    
    public static final int VALUE_NOT_FOUND = -1;
    
    /**
     * 
     */
    public static int binarySearch(int value, int[] list)
    {
        return binarySearch(value, list, 0, list.length - 1);
    }

    // this is the recursive helper version of the method
    private static int binarySearch(int value, int[] list, int start, int end)
    {
        // deal with any possible error cases first
        if (list == null || start > end || end >= list.length || start < 0)
            return VALUE_NOT_FOUND;
           
        // base case is searching a subarray of size one
        if (start == end)
        {
            if (value == list[start])
                return start;
            else 
                return VALUE_NOT_FOUND;
        }
        else
        {
            // compute midpoint
            int middle = (end + start) / 2;
            if (value == list[middle])
                return middle;
            else if (value < middle)
                return binarySearch(value, list, start, middle - 1);
            else 
                return binarySearch(value, list, middle + 1, end);
        }
    }

    // this version is a little more subtle and has cleaner code.  There are probably other ways
    // to accomplish the same thing
    private static int binarySearch2(int value, int[] list, int start, int end)
    {
        // deal with any possible error cases and base case
        if (list == null || start > end || end >= list.length || start < 0)
            return VALUE_NOT_FOUND;
        else
        {
            // compute midpoint
            int middle = (end + start) / 2;
            if (value == list[middle])
                return middle;
            else if (value < middle)
                return binarySearch(value, list, start, middle - 1);
            else 
                return binarySearch(value, list, middle + 1, end);
        }
    }
}