/**
 * 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) an 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 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)
        {
            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
}