public class Search {

  private int comparisons;
  private int calls;

  public Search(){comparisons=0; calls=0;}
  public void reset(){comparisons=0; calls=0;}
  public int stats(){return comparisons;}
  public int calls(){return calls;}

  private int compareTo(String s1, String s2){
    comparisons++;
    int i = s1.compareTo(s2);
    if (i<0)    
      return -1;   // s1 is lexicograhically less than s2
    else if (i>0) 
      return 1;    // s1 is lexicograhically greater than s2
    else 
      return 0;   // s1 is lexicograhically equal to s2
  }

  /*
  public boolean BinarySearch(String[] S, String k, int low, int high){
    int mid = (low + high)/2;
    return low<=high && compareTo(k,S[mid])==0 ||
           (low<=high && compareTo(k,S[mid])==-1 && BinarySearch(S,k,low,mid-1)) ||
           (low<=high && compareTo(k,S[mid])== 1 && BinarySearch(S,k,mid+1,high));
  }
  */

  public boolean BinarySearch(String[] S, String k, int low, int high){
    calls++;
    int mid = (low+high)/2;
    if (low>high)
      return false;
    else if (compareTo(k,S[mid])==-1)
      return BinarySearch(S,k,low,mid-1);
    else if (compareTo(k,S[mid])==1)
      return BinarySearch(S,k,mid+1,high);
    else return false;
  }

 
  public boolean LinearSearch(String[] S, String k, int low, int high){
    boolean found = false;
    for (int i=low; i<=high && !found; i++)
      found = compareTo(k,S[i])==0;
    return found;
  }

}