二分查找

整数二分

1、确定分界点 mid = l + r >> 1
2、判断分界区间，（1）如果查找的值是在左边 ：r = mid，（2）如果是在右边 l = mid

  1. //目标值在右边
  2. private static int binSearch(Integer[] q, int num, int l, int r) {
  4.         while (l < r) {
  5.             int mid = l + r + 1 >> 1;
  6.             if (q[mid] <= num) l = mid;
  7.             else l = mid - 1;
  8.         }
  10.         if (q[l] == num) return l;
  11.         else return -1;
  12.     }
  1. //目标值在左边
  2. private static int binSearch(Integer[] q, int num, int l, int r) {
  4.         while (l < r) {
  5.             int mid = l + r >> 1;
  6.             if (q[mid] >= num) r = mid;
  7.             else l = mid + 1;
  8.         }
  10.         if (q[l] == num) return l;
  11.         else return -1;
  12.     }

浮点数二分（经典问题，求开平方的值）

1、定义分界点 mid = (l + r) / 2
2、不需要考虑边界

  1. public static void main(String[] args) {
  3.         Scanner sc = new Scanner(System.in);
  4.         double x = sc.nextDouble();
  6.         double l = 0;
  7.         double r = x;
  8.         while (r - l > 1e-8){
  9.             double mid = (l + r) / 2;
  10.             if (mid * mid >= x) r = mid;
  11.             else l = mid;
  12.         }
  13.         System.out.println(l);
  14.     }