/**
 * A utility class containg methods for searching through an array.
 *
 * @author  Prof. David Bernstein, James Madison University
 * @version 1.0
 */
public class Searcher
{
    //[0
    /**
     * Search through (part of) a sorted array of Comparable objects
     * for a particular target.
     *
     * @param first  The first index to consider (inclusive)
     * @param last   The last index to consider (inclusive)
     * @param target The Comparable object to search for
     * @param data   The sorted array of Comparable objects
     * @return       The index of the target (or -1 if it isn't found)
     */ 
    public static int search(int first, int last, 
                             Comparable target, Comparable[] data)
    {
        int      left, middle, result, right;
        

        result = -1;
        
        if (first == last) // The base case
        {
            if (target.compareTo(data[first]) == 0)
            {
                result = first;                
            }
        }
        else              // Refinement (i.e., shrink the search space)
        {
            if ((target.compareTo(data[first]) >= 0) &&
                (target.compareTo(data[last])  <= 0))
            {
                middle = (first + last) / 2;
                // Note: This can be done more efficiently.
                //       You should think about how!
                left   = search(first, middle, target, data);
                right  = search(middle + 1, last, target, data);                
                result = Math.max(left, right);
            }
        }
        return result;
    }
    //]0
}