题解 | 二分查找总结
Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky -------Knuth
尽管二分查找的基本理念十分简单明了，但是它的细节queue令人抓狂 ----唐纳德·克努特(KMP发明者)
能不能写对二分查找有以下几个关键点：
- 初始边界值
- 循环条件
- 左侧、右侧如何更新
- 中间点位置选取
严格的统计来讲，二分查找有64种写法，但是重要的是我们能写对其中一种。
tips ：写对二分的技巧是不要用else，而是把每一种情况列出来
下面举例三种常用二分：
1.标准二分
public int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1; // 注意
while(left <= right) { // 注意
int mid = left + (right - left) / 2;
if(nums[mid] == target)
return mid;
else if (nums[mid] < target)
left = mid + 1; // 注意
else if (nums[mid] > target)
right = mid - 1; // 注意
}
return -1;
}初始边界值
初始化 right 的赋值是 nums.length - 1，这意味着我们二分的区间是一个闭区间，即 [left, right] ，这直接决定了我们循环条件的选择。
循环条件
循环条件为 <= 这是由初始边界值决定的，初始边界值决定了我们的区间是一个闭区间，所以为了遍历区间中的每一个数，左右边界值相等的情况也应该进行判断，例如[2, 2]，代表区间中只有一个值2 。
左侧、右侧如何更新
为什么是mid + 1 或 mid - 1 ？因为我们在更新左右边界的时候已经判断过 mid不是我们要找的结果，所以应该略过 mid
2.寻找左边界
int left_bound(int[] nums, int target) {
if (nums.length == 0) return -1;
int left = 0;
int right = nums.length; // 注意
while (left < right) { // 注意
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
right = mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid; // 注意
}
}
// target 比所有数都大
if (left == nums.length) return -1;
// 类似之前算法的处理方式
return nums[left] == target ? left : -1;
}初始边界值
初始化 right 的赋值是 nums.length，这意味着我们二分的区间是一个左闭右开，即 [left, right) ，这直接决定了我们循环条件的选择。
循环条件
循环条件为 < 这是由初始边界值决定的，初始边界值决定了我们的区间是一个左闭右开，这时，左右边界值相等的情况对应着一个空的区间，例如[2, 2)。所以当left == right 时，我们就应该停止循环。
左侧、右侧如何更新
由于我们寻找的是左边界，所以 nums[mid] == target 时，我们应该继续向左寻找，因此应该移动 right ，那么为什么 是 min = right，而不是 mid = right - 1 呢？
原因就在于我们的搜索取件是一个左闭右开区间，我们下一步搜索想要略过 mid 只要搜索区间 [ left，mid ) 即可。而移动 left 是，则由于左侧是闭区间， left = mid + 1 。
这时有人可能会有疑问，这样如果此时 nums[mid]就是边界值，会不会错过边界呢？例如序列0， 1，2，3，3，3，4，5，6，若此时right = 3，下一次搜索区间为 [0 , 3), 会不会错过左边界值呢？
不会！这里要提一下我们的中间点位置选取，我们的选取方式如下：
int mid = left + (right - left) / 2; 这种写法是避免计算是溢出，还有另外一种等价的写法：
int mid = (left + right) / 2;
你可能没有意识到，这么做实际上是在向下取整，例如：
float a = 1,b = 2;
float c = (a + b) / 2;
//毫无疑问，c = 1.5
int a = 1,b = 2;
int c = (a + b) / 2;
//此时，c = 1，向下取整回头注意我们的循环条件当 left == right 时，循环结束，也就是说,循环结束后，left刚好取到左边界。
最后，对特殊情况做一下处理即可：
// target 比序列中所有数都大
if (left == nums.length) return -1;
// target 比序列中所有数都小或不存在目标值
return nums[left] == target ? left : -1;3.寻找右边界
这时有人可能会说，右边界不是左边界的对称吗，然后写出如下代码：
//找右边界
int right_bound(int[] nums, int target) {
if (nums.length == 0) return -1;
int left = 0, right = nums.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
left = mid + 1; // 注意
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid;
}
}
if (left == 0) return -1;//所有数都比目标值大，target比所有数都小
return nums[left-1] == target ? (left-1) : -1; //注意
}初始边界值
同寻找左边界。
循环条件
同寻找左边界。
左侧、右侧如何更新
由于我们寻找的是右边界，所以 nums[mid] == target 时，我们应该继续向右寻找，因此应该移动 left，那么为什么 是 min = left + 1，而不是 mid = left 呢？
原因就在于我们的搜索取件是一个左闭右开区间，我们下一步搜索想要略过 mid 只要搜索区间 [ left，mid ) 即可。
而移动 left 是，则由于左侧是闭区间，下一次搜索区间应该是[ mid + 1, right )，
为什么返回值是 left-1 ？
首先根据循环条件，结束时left == right ，为了对称，也可以返回 right - 1 ；其次，由于nums[mid] > target 时，right = mid ，所以right会一直停留在右边界右边一个，所以结束时返回 right - 1。
另外，右边界代码没有和左边界代码完全对称，原因就在于中间值选取时的向下取整。
最后，对特殊情况作出处理即可：
if (left == 0) return -1;//所有数都比目标值大，target比所有数都小
return nums[left-1] == target ? (left-1) : -1; //注意作者：好吃懒做东
编辑：西瓜媛
本文来自程序媛驿站，未经授权不得转载.
腾讯云开发者
