vlambda博客
学习文章列表

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.5int 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; //注意

编辑：西瓜媛

本文来自程序媛驿站，未经授权不得转载.