二分查找有几种写法？它们的区别是什么？

这句话可以这样理解：思路很简单，细节是魔鬼。

本文就来探究几个最常用的二分查找

场景：寻找一个数、寻找左侧边界（左边第一个比目标值小的数）、寻找右侧边界（右边第一个比目标值大的数）。

零、二分查找框架

另外声明一下，计算 mid 时需要技巧防止溢出：

一、寻找一个数（基本的二分搜索

）

这个场景是最简单的，肯能也是大家最熟悉的，即搜索一个数，如果存在，返回其索引，否则返回 -1。

1.为什么 while 循环的条件中是

首先我们明确一个概念搜索区间的概念，因为初始化 right 的赋值是 n - 1，即最后一个元素的索引，而不是 n.这二者可能出现在不同功能的二分查找中，区别是：前者相当于两端都闭区间 [left, right]，后者相当于左闭右开区间 [left, right)。所以我们的搜索区间就是[left,right],相当与两边都是闭区间。

很显然我们这个算法中使用的是前者的[left,right]区间

那 while 循环什么时候应该终止？while(left

while(left < right) 的终止条件是 left == right，写成区间的形式就是 [left, right]，或者带个具体的数字进去 [2, 2]，这时候区间非空，还有一个数 2，但此时 while 循环终止了。也就是说这区间 [2, 2] 被漏掉了，索引 2 没有被搜索，所以为了查找到我们的目标数值，循环就要用

2.为什么 left = mid + 1，right = mid - 1？我看有的代码是 right = mid 或者 left = mid，没有这些加加减减，到底怎么回事，怎么判断？

其实明白了搜索区间这个概念，我们就知道了这个算法的区间是[left,right]，那搜索完一次，变为[left,mid-1]和[mid+1,right]了。

二、寻找左侧边界的二分搜索

直接看代码，其中的标记是需要注意的细节：

为什么 while(left < right) 而不是

答：用相同的方法分析，因为 right = nums.length 而不是 nums.length - 1 。因此每次循环的「搜索区间」是 [left, right) 左闭右开。

while(left < right) 终止的条件是 left == right，此时搜索区间 [left, left) 为空，所以可以正确终止

2. 为什么没有返回 -1 的操作？如果 nums 中不存在 target 这个值，怎么办？

答：因为要一步一步来，先理解一下这个「左侧边界」有什么特殊含义：

对于这个数组，算法会返回 1。这个 1 的含义可以这样解读：nums 中小于 2 的元素有 1 个。

3. 为什么 left = mid + 1

，right = mid ？和之前的算法不一样？

答：这个很好解释，因为我们的「搜索区间」是 [left, right) 左闭右开，所以当 nums[mid] 被检测之后，下一步的搜索区间应该去掉 mid 分割成两个区间，即 [left, mid) 或 [mid + 1, right)。

4. 为什么该算法能够搜索左侧边界？

答：关键在于对于 nums[mid] == target 这种情况的处理：

可见，找到 target 时不要立即返回，而是缩小「搜索区间」的上界 right，在区间 [left, mid) 中继续搜索，即不断向左收缩，达到锁定左侧边界的目的。

5. 为什么返回 left 而不是 right？

答：都是一样的，因为 while 终止的条件是 left == right。

三、寻找右侧边界的二分查找

寻找右侧边界和寻找左侧边界的代码差不多，只有两处不同，已标注：

为什么这个算法能够找到右侧边界？

答：类似地，关键点还是这里：

当 nums[mid] == target 时，不要立即返回，而是增大「搜索区间」的下界 left，使得区间不断向右收缩，达到锁定右侧边界的目的。

2. 为什么最后返回 left - 1 而不像左侧边界的函数，返回 left？而且我觉得这里既然是搜索右侧边界，应该返回 right 才对。

答：首先，while 循环的终止条件是 left == right，所以 left 和 right 是一样的，你非要体现右侧的特点，返回 right - 1 好了。

至于为什么要减一，这是搜索右侧边界的一个特殊点，关键在这个条件判断：

因为我们对 left 的更新必须是 left = mid + 1，就是说 while 循环结束时，nums[left] 一定不等于 target 了，而 nums[left-1] 可能是 target。

至于为什么 left 的更新必须是 left = mid + 1，同左侧边界搜索，就不再赘述。

热爱技术才能学好技术

每天进步一点点