class BinarySearchConcise {

/*
 * Assumes the data array is sorted in increasing order (and all elements are distinct)
 * Returns the index of query in data if it exists
 * else returns -1
 */
  static int search(int[] data, int query) {
    return searchHelper (data, query, 0, data.length-1);
  }
 
/*
 * 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 searchHelper(int[] data, int query, int startIndex, int endIndex)
  {
    
    if(endIndex<=startIndex) { // base case: array of size 1 or less
      if (endIndex==startIndex && query == data[startIndex])
        return startIndex;
      else
        return -1;
    }
  
    // recursive case: reduce array size by factor of 2 (if even) or approx factor of 2 (if odd)
    int midIndex = (startIndex+endIndex)/2; // Note that midIndex>=startIndex and midIndex<endIndex, because startIndex<endIndex and division rounds down  
    if (query<=data[midIndex])
      return searchHelper(data, query, startIndex, midIndex); // midIndex<endIndex, so we are calling on a smaller array
    else
      return searchHelper(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));
  }
}