import Comparator;

/**
 * Utilities for searching in arrays.
 *
 * @author Carl Caffeinated
 * @author Carla Caffeinated
 */
public class Searcher {
  /** 
   * Determine if a value is in the array.
   */
  public boolean search(Object lookForMe, Object[] lookHere, Comparator compare)
    throws IncomparableException
  {
    return search(lookForMe, lookHere, 0, lookHere.length-1, compare);
  } // search(Object, Object[])
  
  /**
   * Determine if a value is in a subarray.
   */
  protected boolean search(Object lookForMe, Object[] lookHere, 
                           int lb, int ub,
                           Comparator compare) 
    throws IncomparableException
  {
    // Is the subarray empty?  If so, the object can't be there.
    if (ub < lb) return false;
    // Otherwise, it must be in the middle, left half, or right half.
    int mid = (lb + ub) / 2;
    return ( compare.equals(lookForMe, lookHere[mid]) ||
             search(lookForMe, lookHere, lb, mid-1, compare) ||
             search(lookForMe, lookHere, mid+1, ub, compare) );
  } // search(Object, Object[], int, int)
} // class Searcher