算法基础学习——二分查找（附带Java模板）

有单调性的数列一定可以使用二分，没有单调性的题目也可能可以使用二分；

（一）整数二分

二分的本质：

在某个整数区间内，存在某种性质使得区间内左半边的数都不满足该性质；而右半边的数都满足该性质；那么二分的作用就是找到左右这两个分界点；

1.找满足红色性质的边界点（如图上）

如果是让l等于mid（即找左半边的分界点）则要记得mid = (l+r+1)/2

2.找满足绿色性质的边界点（如图上）

如果是让r等于mid（即找右半边的分界点）则mid = (l+r)/2，不用另外加1；

情况1为什么额外加1？ 答：因为在程序中，(l+r)/2是向下取整；当遇到遇到r=l+1（l和r只相差1，数组只有两个元素）的情况，(l+r)/2就等于l，这时候mid=(l+r)/2就是mid=l如下图所示：这次循环相当于没有变化，再次循环也不会有变化，进入死循环；

基本思想：不断缩小答案区间，当区间长度为一时，就是答案；

时间复杂度：平均O(logn)

步骤：

先写出基本模板:mid = (l+r)/2
定义判断条件check()函数
看应该是让l=mid还是r=mid；如果应该l=mid则把前面的mid改为 mid=(l+r+1)/2

模板：

// 检查x是否满足某种性质  
private static boolean check(int x) {  /* ... */  
}  // 区间[left, right]被划分成[left, mid]和[mid + 1, right]时使用： 
// 或者称之为左二分查询，查找左侧第一个满足条件的数
private static int leftBinarySearch(int[] arr, int left, int right) {  while (left < right) {  int mid = arr[left + right >> 1];  if (check(mid)) {  right = mid;    // check()判断mid是否满足性质  } else {  left = mid + 1;  }  }  return left;  
}  // 区间[left, right]被划分成[left, mid - 1]和[mid, right]时使用：  
// 或者称之为右二分查询，查找右侧最后一个满足条件的数
private static int rightBinarySearch(int[] arr, int left, int right) {  while (left < right) {  int mid = arr[left + right + 1 >> 1];  if (check(mid)) {  left = mid;    // check()判断mid是否满足性质  } else {  right = mid - 1;  // 有加必有减}  }  return left;  
}

（二）浮点数二分

典型问题：求一个数的平方根

基本思想：不断缩小答案区间，当区间长度足够小时（即左右边界之差足够小），边界的值就约等于答案；

时间复杂度：平均O(logn)

步骤：

mid就等于(r+l)/2;
while循环判定条件为r-l>1e-8（左右边界之差足够小时结束循环）

模板：

// 检查x是否满足某种性质  
private static boolean check(int x) {  /* ... */  
}  // 区间[left, right]被划分成[left, mid]和[mid + 1, right]时使用： 
// 或者称之为左二分查询，查找左侧第一个满足条件的数
private static int leftBinarySearch(int[] arr, int left, int right) {  while (left < right) {  int mid = arr[left + right >> 1];  if (check(mid)) {  right = mid;    // check()判断mid是否满足性质  } else {  left = mid + 1;  }  }  return left;  
}  // 区间[left, right]被划分成[left, mid - 1]和[mid, right]时使用：  
// 或者称之为右二分查询，查找右侧最后一个满足条件的数
private static int rightBinarySearch(int[] arr, int left, int right) {  while (left < right) {  int mid = arr[left + right + 1 >> 1];  if (check(mid)) {  left = mid;    // check()判断mid是否满足性质  } else {  right = mid - 1;  // 有加必有减}  }  return left;  
}

注意点：