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)
  {
    
    if (endIndex<startIndex) // this prevents accessing the array on an out-of-bounds index AND works as a base case
      return -1;
 
    int midIndex = (startIndex+endIndex)/2; // Note that midIndex>=startIndex and midIndex<=endIndex, because startIndex<=endIndex
   
    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); // midIndex-1<endIndex, so we are calling on a smaller array
    else
      return search(data, query, midIndex+1,endIndex); // midIndex+1>startIndex, so we are calling on a smaller array
  }
  
  public static void main(String[] args) {
    int [] data={3, 5, 7, 9, 11};
    System.out.println(search(data, 4, 0, data.length-1));
  }
}