public class BinarySearch {
  public static <T extends Comparable<? super T>> int search(T arr[], T value) {
    int left = 0;
    int right = arr.length - 1;
    while (left <= right) {
      int mid = (left & right) + ((left ^ right) >> 1);
      if (arr[mid].compareTo(value) == 0) {
        return mid;
      } else if (arr[mid].compareTo(value) > 0) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }
    return -1;
  }
 
  public static void main(String[] args) {
    Integer[] arr = new Integer[]{1, 3, 3, 6, 7, 9};
 
    //-1
    System.out.println(search(arr, 0));
 
    //0
    System.out.println(search(arr, 1));
 
    //5
    System.out.println(search(arr, 9));
 
    //-1
    System.out.println(search(arr, 10));
 
    //2
    System.out.println(search(arr, 3));
  }
}　

public class BinarySearch {
  public static <T extends Comparable<? super T>> int findFirst(T arr[], T value) {
    int left = 0;
    int right = arr.length - 1;
    //当left>=right时退出，这里的“=”情况与二分不同
    while (left < right) {
      int mid = (left + right) >> 1;
      if (arr[mid].compareTo(value) < 0) {
        left = mid + 1;
      } else {
        right = mid;
      }
    }
    // 上面循环遍历完后。是找到了value值？还是没找到value值？判断一下。
    if (arr[left] == value) {
      return left;
    } else {
      return -1;
    }
  }
 
  public static void main(String[] args) {
    Integer[] arr = new Integer[]{1, 3, 3, 3, 3, 3, 3, 3, 3, 3, 6, 7, 9};
 
    //-1
    System.out.println(findFirst(arr, 0));
 
    //0
    System.out.println(findFirst(arr, 1));
 
    //12
    System.out.println(findFirst(arr, 9));
 
    //-1
    System.out.println(findFirst(arr, 10));
 
    //1
    System.out.println(findFirst(arr, 3));
  }
}

public class BinarySearch {
  public static <T extends Comparable<? super T>> int fewer(T arr[], T value) {
    int left = 0;
    int right = arr.length - 1;
    //当left > right 时退出
    while (left <= right) {
      int mid = (left & right) + ((left ^ right) >> 1);
      if (value.compareTo(arr[mid]) <= 0) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }
    return right;
  }
 
  public static void main(String[] args) {
    Integer[] arrF = new Integer[]{21, 23, 25, 25, 31, 34, 37, 39, 52, 63};
 
    //3
    System.out.println(fewer(arrF, 30));
  }
}