public class BinarySearch {
  /**
   * Returns index of element x in sorted array arr
   * <p>
   * Generic method that searches for an element in a sorted array using binary search.
   * The generic element type should implement Comparable
   *
   * @param  x   the element to search for
   * @param  arr the array sorted according to Comparable ascending order
   * @return     an index i for which arr[i].compareTo(x) == 0 or
   *             -1 if no such index exists 
   */
  public static <T extends Comparable<T>> int binarySearch(T x, T[] arr) {
    int l = 0, r = arr.length - 1;
    while (l <= r) {
      int m = (l + r) / 2;
      int c = x.compareTo(arr[m]);
      if (c < 0) {  // x must be to the left of m
          r = m - 1;
      } else if (c > 0) {  // x must be to the right of m
          l = m + 1;
      } else {  // c == 0, found x (an element equal to x according to compareTo)
          return m;
      }
    }
    // did not find x
    return -1;
  }
  
  public static void main(String[] args) {
    Integer[] arr = {2, 5, 7, 8, 10, 13, 17, 18, 19, 21, 25, 32, 35, 36, 39, 42};
    System.out.println(binarySearch(7, arr));
 }
}