二分查找的通用模板

二分查找适用于对于有序数组的精确查找，例如从一个有序数组中找到指定元素的索引，可将时间复杂度从普通枚举的 O(n) 降至 O(log n) ，前提是数组必须是有序的，否则是没有办法使用二分查找的。二分查找的思想虽然简单，不过在实现过程中会有很多细节问题需要注意，例如判断循环是用left < right还是用left <= right，right是取最右的元素还是取数组的边界。本文想通过七个例题，约定一种规则或是模板，从此让写二分查找不再出现模棱两可的局面。

规则约定

1. left统一采用数组最左端即下标为0，right采用数组最右端的元素（非边界）,这样二分查找的范围是一个闭区间[left,right]，包括扫描两端的元素；
2. while中统一使用left<=right，如果不加=，退出循环的条件是left==right，而我们采用的是[left,right]的闭区间，left和right相等时依然是有效区间，所以left==right时应继续进入循环查找，否则会导致元素遗漏;
3. 既然采用[left,right]闭区间，当确定mid不是查找元素时，那么将数组一分为二成[left,mid-1]和[mid 1,right]，mid排除在外。

这只是我们约定的规则，二分查找会有很多种写法，本文的目的是就是想通过一个统一的规则，使得在写二分查找时不再纠结于各种细节，遵循这个规则就行了。

左区间和右区间

在二分搜索的应用中，除了查找目标值，还有一种应用是不断折半缩小范围，直到剩下最后一个元素。这种情况并不能排除mid，而是以mid作为新的边界，这样一来会产生2种分界情况，即中间数在左范围或者中间数在右范围：

1. [left,mid]和[mid 1,right]
2. [left,mid-1]和[mid,right]

对于情况1，中间数在左范围：

对于情况2，中间数在右范围：

我们可以根据题意选择中间数归在左范围还是右范围，但值得注意的是，这2种情况选择中间数的位置是不一样的，对于左范围，中间数的选择是mid=(left right)//2，而对于右范围，中间数的选择是(left right 1)//2，即中间数的选择更靠右一些。

试想一下，如果我们按照情况2中间数在右范围的逻辑，同时又将中间数设置为了mid=(left right)//2即中间数更靠左，那么当只有2个元素[a,b]的情况，a会被选为中间数，那么被分割的2个区间分别会是[]和[a,b]，这并不符合我们的预期。如果进入第一个区间，该区间为空，会退出循环执行到原本永远不会执行的return -1，进入到第二个区间，则该区间和原区间一致，会导致死循环。

例题一：从有序数组中查找指定元素，数组不包含重复元素

最基本的二分查找问题，根据我们的约定规则，代码如下：

注意：在有的编程语言中mid=(left right)//2这句可能因为left right过大导致整型溢出，可替换成mid=left (right-left)//2，先减后加。 上面的代码为了演示，展示了所有的条件，实际else if是可以省略的，简单调整下：

例题二：从有序数组中查找指定元素，数组包含重复元素，返回最左边的索引

这题和例题一的区别在于，数组包含了重复元素，找到了元素还不行，我们得找最左边的索引，修改思路是如果中间值等于目标值了，并不能直接返回，依然搜索左边。 上一题中，我们将数组划分为了[left,mid]和[mid 1,right]，当mid不等于target时，mid可以排除掉，接下来搜索[left,mid-1]或者[mid 1,right]，这是没有问题的，但这一题中当mid等于target时，仍然要往左边搜索，所以要搜索[left,mid]，而并不是[left,mid-1]，否则你将会错过mid这个元素。 注意：由于将mid纳入了重复搜索区间，所以当只剩一个元素的时候一定要返回，否则会无法退出循环。

相比于例题一，我们仅仅是改变了返回条件。

例题三：从有序数组中查找指定元素，数组包含重复元素，返回最右边的索引

和例题二几乎一模一样，只是换成了返回最右边的索引，主要是观察下左和右有什么区别： 区别就在于当mid等于target时，我们要搜索右边，我们可能会想当然的将上题的right=mid改成left=mid，但是这样是有问题的。 因为mid总是向下舍入的，会更靠近left，想想当只有2个元素的时候，left会始终等于mid，这样将导致无法往右搜索，陷入死循环。 解法办法是让mid更靠近right，也就是让区间划分为[left,mid-1]和[mid,right]，只需做一个小改动即可，设置mid=(left right 1)//2。

关于中位数靠右的例子，还可以参考我在这个问题69. x 的平方根的二分查找解法。 这2道题实际是可以把left==right抽离出来的，代码可能显得更美观，可对比参考搜索左边界和右边界这2段优化后的代码有什么不同：

个人强烈建议先按模板来，这样可避免增加记忆成本，比如上面这2题，最后返回你必须思考是返回left还是right，因为最后的返回包含了left==right或者left>right两种情况，当相等时无论返回left或是right都不影响结果，而当超出时，2个方法是有区别的：第1个方法只有left指针是安全的，right指针可能会超出数组边界；同理，第2个方法只有right指针是安全的，left指针可能会超出数组边界。因为我们改变了模板，将2种结果合并返回了，这是值得注意的地方。 而套用模板，你只需思考每轮结束后，下一轮应该搜索的区间是什么，以及什么时候该返回结果，最后再想想有没有重复的判断可以抽离出来的（这一步实际上可有可无，毕竟除了让代码变少，对时间复杂度没有什么影响）。 接下来进阶看看更难的例子。

例题四：从旋转排序数组中查找指定元素，数组不包含重复元素

旋转排序数组是指有序数组在某一个点进行了旋转而得到数组，例如[0,1,2,4,5,6,7]变化成为[4,5,6,7,0,1,2]，当然旋转排序数组也包括完全升序的数组，比如[0,1,2,4,5,6,7]也算旋转排序数组。 继续套用这个模板，和有序二分查找类似，当找到target的时候直接返回，没有找到，则继续搜索左边或者右边，每次将搜索范围缩小至二分之一，不过这里的难点在于，如何判断是搜索左边还是搜索右边。 通过观察可发现，当将一个旋转排序数组从任意某个点一分为二的时候，拆出的两部分中其中一个一定是递增有序的。 实际上，我们从mid将旋转排序数组一分为二的时候，只有这三种情况：

1. 左半部分[left,mid]完全递增升序，右半部分[mid 1,right]非完全递增升序；
2. 左半部分[left,mid]非完全递增升序，右半部分[mid 1,right]完全递增升序；
3. 左半部分[left,mid]和右半部分[mid 1,right]都是完全递增升序，mid 1正好是数组中的最小值。

我们通过这个规律，可以只从这个递增有序的部分进行判断，因为是递增升序的，左边最小，右边最大，可以确定target是否在这个部分，如果在就搜索这部分，否则就排除这部分，去另外那个部分搜索。 而用mid将数组一分为二之后，通过nums[left]<=nums[mid]即可判断左部分是否递增有序，如果左部分不是，那右部分就肯定是递增升序了。 注意：这里一定是<=，因为mid是向下舍入的，会靠近left，当left==mid即只有一个元素时，我们也认为是递增升序的。 总结：

1. 将数组从中间拆分为[left,mid]和[mid 1,right]两部分；
2. 从拆分的两部分中找到递增有序的那部分；
3. 检查target是否在这个递增有序的部分中（因为是递增升序，很容易判断target是否在这个部分）；
4. 确定target在这个部分，继续搜索这个部分，排除target在这个部分，则搜索另一个部分。

例题五：从旋转排序数组中查找指定元素，数组包含重复元素

思路和例题四一样，不过由于存在重复元素，我们无法通过nums[left]<=nums[mid]判断左部分是否递增升序了，比如数组[1,3,1,1,1]，nums[left]等于1，nums[mid]也等于1，但左部分显然不是递增升序的。 如何处理这个问题，有个简单办法，当相等的时候将left右移一位，相当于排除一个元素，再继续搜索。 相较例题四，只需把相等的情况抽离出来单独判断即可：

不可避免的这个方法失去了一部分效率，在极端情况下，比如[1,1,1,1,1,1,1,1,1,1,0]时间复杂度降到了 O(n) ，由于只是对相同元素的情况做了特殊处理，所以该代码其实完全适用于例题四。

例题六：从旋转排序数组中查找最小值，数组不包含重复元素

和例题四一样，不过不是查找指定元素，而是查找最小元素。 继续套用模板，这里根据旋转排序数组特征，思路如下：

1. 如果数组是完全升序，即nums[left]<nums[right]直接返回最左边的元素，因为肯定是最小的；
2. 当搜索到只有一个元素，即left==right,这个元素一定是最小元素，和查找指定元素不同，数组是一定存在最小值的，所以问题一定有解；
3. 如果非完全升序，将数组从中间拆分为[left,mid]和[mid 1,right]两部分，同理，这两部分中其中一部分一定是递增升序的；
4. 数组是非完全升序，而左部分[left,mid]又是递增升序的，那么最小元素一定在右部分，搜索右部分；
5. 如果左部分非完全升序，则继续搜索左部分[left,mid]，将right设置为mid。

注意：这里和二分查找指定元素是有区别的，二分查找指定元素是可以排除mid的，因为一开始就比较了nums[mid]和target是否相等，而这里并不能确定nums[mid]是否是最小值，只能将搜索范围从[left,right]缩小至[left,mid]或者[mid 1,right]，所以要么left变成mid 1，要么right变成mid。这也是二分查找的核心思想，每轮将搜索范围缩小一半。

可以发现当left和right相等时，循环内部直接返回了，所以循环外的return -1是永远不会执行的。这当然也是符合逻辑的，因为数组中一定会存在最小元素，不可能返回-1。 这里可以将循环条件改成left<right，排除掉相等的情况，这样退出循环的条件是left==right，代表只剩一个元素，最后无论返回left或是right都是一样的。 优化后的代码：

或许这样的代码看上去更漂亮，但我还是建议新手朋友不要一上来就思考这样写，因为除了增加记忆成本外，并不会降低时间复杂度。

例题七：从旋转排序数组中查找最小值，数组包含重复元素

和例题五一样，由于存在相同的元素，所以相等的情况要排除在外。 步骤依然和例题六思路一样，仅在第4步做了调整，将nums[left]==nums[mid]情况单独抽离出来：

1. 如果数组是完全升序，即nums[left]<nums[right]直接返回最左边的元素，因为肯定是最小的，不变；
2. 当搜索到只有一个元素，即left==right,这个元素一定是最小元素，和查找指定元素不同，数组是一定存在最小值的，所以问题一定有解，不变；
3. 如果非完全升序，将数组从中间拆分为[left,mid]和[mid 1,right]两部分，同理，这两部分中其中一部分一定是递增升序的，不变；
4. 数组是非完全升序，而左部分[left,mid]又是递增升序的，那么最小元素一定在右部分，搜索右部分，当nums[left]==nums[mid]时，并不能确定左部分是否完全升序，将left右移一位排除一个元素；
5. 如果左部分非完全升序，则继续搜索左部分[left,mid]，将right设置为mid，不变；

时间复杂度为 O(log n) ，最坏情况时间复杂度为 O(n) 。

总结

排除一些特殊案例，我们的模板大致是这样：

1. 采用左右闭区间作为搜索范围;
2. 确定区间划分为（[left,mid]和[mid 1,right]）或者（[left,mid-1]和[mid,right]），即mid靠左或靠右；
3. 经过判断后，确定搜索范围应该缩小在左半部分（修改right）或是右半部分（修改left），注意左右的边界元素是包含在内的；
4. 退出循环的条件是left>right，确定你该在何时返回结果。

家庭作业

问题：在山脉数组中查找目标值。 给你一个山脉数组，你要从中找到目标值target的最小下标，即如果存在多个target取索引较小的那个，如果不存在则返回-1。 山脉数组是指存在一个最大值下标i，它的左边都是递增上升的，右边都是递增下降的，用数学描述是这样： 设山脉数组为A，那么

1. 首先，A.length >= 3
2. 其次，在 0 < i < A.length - 1 条件下，存在 i 使得： A[0] < A[1] < … A[i-1] < A[i] A[i] > A[i 1] > … > A[A.length - 1]

提示： 此题可以说是将前面几道例题结合起来的综合应用，可以分3个步骤解决：

1. 先找到数组中的最大值的索引，将数组从这个位置一分为二；
2. 从左边的递增序列中找target，找到即返回，左边的target索引肯定比右边的索引小；
3. 左边没找到，就从右边的递减序列中找，找到即返回，没找到则返回-1。

步骤2和步骤3就是从有序数组中查找指定元素，这就是二分查找的最基本问题。 步骤1是要从山脉数组中找到最大值，这个问题我们例题中尚未提到过，不过也不难解决。 将数组拆分成[left,mid]和[mid 1,right]两部分，当nums[mid]<nums[mid 1]时，峰值肯定在右半部分，否则就在左半部分，而由于峰值只会有一个，所以当搜索范围缩小到left==right即只有一个元素时，这个值就是最大值。 相信通过套用这个模板，你很快就能写出代码，而这题在leetcode中已经达到了hard级别，想想应该也没有那么难，感兴趣的朋友可以试一试： 力扣入口：1095. 山脉数组中查找目标值