// WARNING: BUGGY!!!
class BinarySearch {
/*
 * Assumes the data array is sorted in increasing order (and all elements are distinct)
 * Returns the index of query in data if it is between startIndex and endIndex inclusive
 * else returns -1
 */
  static int search(int[] data, int query, int startIndex, int endIndex)
  {
    int midIndex = (startIndex+endIndex)/2;
    
    if(endIndex==startIndex) {
      if (query == data[startIndex])
        return startIndex;
      else
        return -1;
    }
    
    
    if (query == data[midIndex])
      return midIndex;
    else if (query<data[midIndex])
      return search(data, query, startIndex, midIndex-1);
    else
      return search(data, query, midIndex+1,endIndex);
  }
  
  public static void main(String[] args) {
    int [] data={3, 5, 7, 9, 11};
    System.out.println(search(data, 8, 0, data.length-1));
  }
}