class BinarySearchIterative {
/*
 * 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)
  {
    int startIndex = 0, endIndex = data.length-1;
    while (startIndex<endIndex) {    
      // each iteration reduces 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])
        endIndex = midIndex; // midIndex<endIndex, so we are iterating on a smaller array
      else
        startIndex = midIndex+1; // midIndex+1>startIndex, so we are iterating on a smaller array      
    }
      
    if (endIndex==startIndex && query == data[startIndex])
      return startIndex;
    else
      return -1;
    
    
  }
  public static void main(String[] args) {
    int [] data={3, 5, 7, 9, 11};
    System.out.println(search(data, 10));
  }
}