二分查找的通用模板
二分查找适用于对于有序数组的精确查找，例如从一个有序数组中找到指定元素的索引，可将时间复杂度从普通枚举的 O(n) 降至 O(log n) ，前提是数组必须是有序的，否则是没有办法使用二分查找的。二分查找的思想虽然简单，不过在实现过程中会有很多细节问题需要注意，例如判断循环是用left < right还是用left <= right，right是取最右的元素还是取数组的边界。本文想通过七个例题，约定一种规则或是模板，从此让写二分查找不再出现模棱两可的局面。
规则约定
- left统一采用数组最左端即下标为0，right采用数组最右端的元素（非边界）,这样二分查找的范围是一个闭区间[left,right]，包括扫描两端的元素；
- while中统一使用left<=right，如果不加=，退出循环的条件是left==right，而我们采用的是[left,right]的闭区间，left和right相等时依然是有效区间，所以left==right时应继续进入循环查找，否则会导致元素遗漏;
- 既然采用[left,right]闭区间，当确定mid不是查找元素时，那么将数组一分为二成[left,mid-1]和[mid+1,right]，mid排除在外。
这只是我们约定的规则，二分查找会有很多种写法，本文的目的是就是想通过一个统一的规则，使得在写二分查找时不再纠结于各种细节，遵循这个规则就行了。
左区间和右区间
在二分搜索的应用中，除了查找目标值，还有一种应用是不断折半缩小范围，直到剩下最后一个元素。这种情况并不能排除mid，而是以mid作为新的边界，这样一来会产生2种分界情况，即中间数在左范围或者中间数在右范围：
[left,mid]和[mid+1,right][left,mid-1]和[mid,right]
对于情况1，中间数在左范围：
123456789 | while left<=right: mid=(left+right)//2 # 中间数在左范围 if left==right: # 只剩最后一个元素，返回结果 return ... if ...: # 判断mid是否满足条件，如果满足继续搜索左范围 right=mid else: # 如果不满足则搜索右范围 left=mid+1return -1 #永远不会执行 |
|---|
对于情况2，中间数在右范围：
123456789 | while left<=right: mid=(left+right+1)//2 # 中间数在右范围 if left==right: # 只剩最后一个元素，返回结果 return ... if ...: # 判断mid是否满足条件，如果满足继续搜索右范围 left=mid else: # 如果不满足则搜索左范围 right=mid-1return -1 #永远不会执行 |
|---|
我们可以根据题意选择中间数归在左范围还是右范围，但值得注意的是，这2种情况选择中间数的位置是不一样的，对于左范围，中间数的选择是mid=(left+right)//2，而对于右范围，中间数的选择是(left+right+1)//2，即中间数的选择更靠右一些。
试想一下，如果我们按照情况2中间数在右范围的逻辑，同时又将中间数设置为了mid=(left+right)//2即中间数更靠左，那么当只有2个元素[a,b]的情况，a会被选为中间数，那么被分割的2个区间分别会是[]和[a,b]，这并不符合我们的预期。如果进入第一个区间，该区间为空，会退出循环执行到原本永远不会执行的return -1，进入到第二个区间，则该区间和原区间一致，会导致死循环。
例题一：从有序数组中查找指定元素，数组不包含重复元素
最基本的二分查找问题，根据我们的约定规则，代码如下：
1234567891011 | def binarySearch(self, nums: List[int], target: int) -> int: left,right=0,len(nums)-1 while left<=right: mid=(left+right)//2 if nums[mid]==target: return mid elif nums[mid] < target: left = mid + 1 elif nums[mid] > target: right = mid - 1 return -1 #未找到任何匹配元素，返回-1 |
|---|
注意：在有的编程语言中mid=(left+right)//2这句可能因为left+right过大导致整型溢出，可替换成mid=left+(right-left)//2，先减后加。
上面的代码为了演示，展示了所有的条件，实际else if是可以省略的，简单调整下：
1234567891011 | def binarySearch(self, nums: List[int], target: int) -> int: left,right=0,len(nums)-1 while left<=right: mid=(left+right)//2 if nums[mid]==target: return mid if nums[mid] < target: left = mid + 1 else: right = mid - 1 return -1 |
|---|
例题二：从有序数组中查找指定元素，数组包含重复元素，返回最左边的索引
这题和例题一的区别在于，数组包含了重复元素，找到了元素还不行，我们得找最左边的索引，修改思路是如果中间值等于目标值了，并不能直接返回，依然搜索左边。
上一题中，我们将数组划分为了[left,mid]和[mid+1,right]，当mid不等于target时，mid可以排除掉，接下来搜索[left,mid-1]或者[mid+1,right]，这是没有问题的，但这一题中当mid等于target时，仍然要往左边搜索，所以要搜索[left,mid]，而并不是[left,mid-1]，否则你将会错过mid这个元素。
注意：由于将mid纳入了重复搜索区间，所以当只剩一个元素的时候一定要返回，否则会无法退出循环。
12345678910111213 | def leftBound(self, nums: List[int], target: int) -> int: left,right=0,len(nums)-1 while left<=right: if left==right: return left if nums[left]==target else -1 #只剩一个元素时，返回结果 mid=(left+right)//2 if nums[mid]==target: right=mid #相等时，右边界变成mid，搜索[left,mid] elif nums[mid]<target: left=mid+1 #搜索[mid+1,right] else: right=mid-1 #搜索[left,mid-1] return -1 |
|---|
相比于例题一，我们仅仅是改变了返回条件。
例题三：从有序数组中查找指定元素，数组包含重复元素，返回最右边的索引
和例题二几乎一模一样，只是换成了返回最右边的索引，主要是观察下左和右有什么区别：
区别就在于当mid等于target时，我们要搜索右边，我们可能会想当然的将上题的right=mid改成left=mid，但是这样是有问题的。
因为mid总是向下舍入的，会更靠近left，想想当只有2个元素的时候，left会始终等于mid，这样将导致无法往右搜索，陷入死循环。
解法办法是让mid更靠近right，也就是让区间划分为[left,mid-1]和[mid,right]，只需做一个小改动即可，设置mid=(left+right+1)//2。
12345678910111213 | def rightBound(self, nums: List[int], target: int) -> int: left,right=0,len(nums)-1 while left<=right: if left==right: return left if nums[left]==target else -1 #只剩一个元素时，返回结果，这里left和right值相等，无区别 mid=(left+right+1)//2 #mid划分为右区间 if nums[mid]==target: left=mid #相等时，左边界变成mid，搜索[mid,right] elif nums[mid]<target: left=mid+1 #搜索[mid+1,right] else: right=mid-1 #搜索[left,mid-1] return -1 |
|---|
关于中位数靠右的例子，还可以参考我在这个问题69. x 的平方根的二分查找解法。
这2道题实际是可以把left==right抽离出来的，代码可能显得更美观，可对比参考搜索左边界和右边界这2段优化后的代码有什么不同：
1234567891011121314151617181920212223 | def leftBound(self, nums: List[int], target: int) -> int: left,right=0,len(nums)-1 while left<right: #去掉了=，相等时就退出循环 mid=(left+right)//2 #mid划分为左区间 if nums[mid]==target: right=mid #右边界变成mid，搜索[left,mid] elif nums[mid]<target: left=mid+1 else: right=mid-1 return left if nums[left]==target else -1 #返回left，这里会有2种情况，left==right或者left>right，只有返回left才是安全的def rightBound(self, nums: List[int], target: int) -> int: left,right=0,len(nums)-1 while left<right: #去掉了=，相等时就退出循环 mid=(left+right+1)//2 #mid划分为右区间 if nums[mid]==target: left=mid #左边界变成mid，搜索[mid,right] elif nums[mid]<target: left=mid+1 else: right=mid-1 return right if nums[right]==target else -1 #返回right，这里会有2种情况，left==right或者left>right，只有返回right才是安全的 |
|---|
个人强烈建议先按模板来，这样可避免增加记忆成本，比如上面这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将旋转排序数组一分为二的时候，只有这三种情况：
- 左半部分[left,mid]完全递增升序，右半部分[mid+1,right]非完全递增升序；
- 左半部分[left,mid]非完全递增升序，右半部分[mid+1,right]完全递增升序；
- 左半部分[left,mid]和右半部分[mid+1,right]都是完全递增升序，
mid+1正好是数组中的最小值。
我们通过这个规律，可以只从这个递增有序的部分进行判断，因为是递增升序的，左边最小，右边最大，可以确定target是否在这个部分，如果在就搜索这部分，否则就排除这部分，去另外那个部分搜索。
而用mid将数组一分为二之后，通过nums[left]<=nums[mid]即可判断左部分是否递增有序，如果左部分不是，那右部分就肯定是递增升序了。
注意：这里一定是<=，因为mid是向下舍入的，会靠近left，当left==mid即只有一个元素时，我们也认为是递增升序的。
总结：
- 将数组从中间拆分为[left,mid]和[mid+1,right]两部分；
- 从拆分的两部分中找到递增有序的那部分；
- 检查target是否在这个递增有序的部分中（因为是递增升序，很容易判断target是否在这个部分）；
- 确定target在这个部分，继续搜索这个部分，排除target在这个部分，则搜索另一个部分。
1234567891011121314151617 | def search(self, nums: List[int], target: int) -> int: left,right=0,len(nums)-1 while left<=right: mid=(left+right)//2 if nums[mid]==target: return mid if nums[left]<=nums[mid]: #判断左部分是否递增升序，注意：这里一定是<= if nums[left]<=target<nums[mid]: right=mid-1 else: left=mid+1 else: if nums[mid+1]<=target<=nums[right]: left=mid+1 else: right=mid-1 return -1 |
|---|
例题五：从旋转排序数组中查找指定元素，数组包含重复元素
思路和例题四一样，不过由于存在重复元素，我们无法通过nums[left]<=nums[mid]判断左部分是否递增升序了，比如数组[1,3,1,1,1]，nums[left]等于1，nums[mid]也等于1，但左部分显然不是递增升序的。
如何处理这个问题，有个简单办法，当相等的时候将left右移一位，相当于排除一个元素，再继续搜索。
相较例题四，只需把相等的情况抽离出来单独判断即可：
12345678910111213141516171819 | def search(self, nums: List[int], target: int) -> int: left,right=0,len(nums)-1 while left<=right: mid=(left+right)//2 if nums[mid]==target: return mid if nums[left]==nums[mid]: left+=1 elif nums[left]<nums[mid]: if nums[left]<=target<nums[mid]: right=mid-1 else: left=mid+1 else: #nums[left]>nums[mid] if nums[mid+1]<=target<=nums[right]: left=mid+1 else: right=mid-1 return -1 |
|---|
不可避免的这个方法失去了一部分效率，在极端情况下，比如[1,1,1,1,1,1,1,1,1,1,0]时间复杂度降到了 O(n) ，由于只是对相同元素的情况做了特殊处理，所以该代码其实完全适用于例题四。
例题六：从旋转排序数组中查找最小值，数组不包含重复元素
和例题四一样，不过不是查找指定元素，而是查找最小元素。 继续套用模板，这里根据旋转排序数组特征，思路如下：
- 如果数组是完全升序，即
nums[left]<nums[right]直接返回最左边的元素，因为肯定是最小的； - 当搜索到只有一个元素，即
left==right,这个元素一定是最小元素，和查找指定元素不同，数组是一定存在最小值的，所以问题一定有解； - 如果非完全升序，将数组从中间拆分为
[left,mid]和[mid+1,right]两部分，同理，这两部分中其中一部分一定是递增升序的； - 数组是非完全升序，而左部分
[left,mid]又是递增升序的，那么最小元素一定在右部分，搜索右部分； - 如果左部分非完全升序，则继续搜索左部分
[left,mid]，将right设置为mid。
注意：这里和二分查找指定元素是有区别的，二分查找指定元素是可以排除mid的，因为一开始就比较了nums[mid]和target是否相等，而这里并不能确定nums[mid]是否是最小值，只能将搜索范围从[left,right]缩小至[left,mid]或者[mid+1,right]，所以要么left变成mid+1，要么right变成mid。这也是二分查找的核心思想，每轮将搜索范围缩小一半。
12345678910111213 | def findMin(self, nums: List[int]) -> int: left,right=0,len(nums)-1 while left<=right: if left==right: return nums[left] if nums[left]<nums[right]: return nums[left] mid=(left+right)//2 if nums[left]<=nums[mid]: left=mid+1 else: right=mid #注意：并不是mid-1 return -1 #永远不会执行 |
|---|
可以发现当left和right相等时，循环内部直接返回了，所以循环外的return -1是永远不会执行的。这当然也是符合逻辑的，因为数组中一定会存在最小元素，不可能返回-1。
这里可以将循环条件改成left<right，排除掉相等的情况，这样退出循环的条件是left==right，代表只剩一个元素，最后无论返回left或是right都是一样的。
优化后的代码：
1234567891011 | def findMin(self, nums: List[int]) -> int: left,right=0,len(nums)-1 while left<right: if nums[left]<nums[right]: return nums[left] mid=(left+right)//2 if nums[left]<=nums[mid]: left=mid+1 else: right=mid return nums[left] |
|---|
或许这样的代码看上去更漂亮，但我还是建议新手朋友不要一上来就思考这样写，因为除了增加记忆成本外，并不会降低时间复杂度。
例题七：从旋转排序数组中查找最小值，数组包含重复元素
和例题五一样，由于存在相同的元素，所以相等的情况要排除在外。
步骤依然和例题六思路一样，仅在第4步做了调整，将nums[left]==nums[mid]情况单独抽离出来：
- 如果数组是完全升序，即
nums[left]<nums[right]直接返回最左边的元素，因为肯定是最小的，不变； - 当搜索到只有一个元素，即
left==right,这个元素一定是最小元素，和查找指定元素不同，数组是一定存在最小值的，所以问题一定有解，不变； - 如果非完全升序，将数组从中间拆分为[left,mid]和[mid+1,right]两部分，同理，这两部分中其中一部分一定是递增升序的，不变；
- 数组是非完全升序，而左部分[left,mid]又是递增升序的，那么最小元素一定在右部分，搜索右部分，当
nums[left]==nums[mid]时，并不能确定左部分是否完全升序，将left右移一位排除一个元素； - 如果左部分非完全升序，则继续搜索左部分[left,mid]，将right设置为mid，不变；
123456789101112131415 | def findMin(self, nums: List[int]) -> int: left,right=0,len(nums)-1 while left<=right: if left==right: return nums[left] #或者return nums[right] if nums[left]<nums[right]: return nums[left] mid=(left+right)//2 if nums[left]==nums[mid]: left+=1 elif nums[left]<nums[mid]: left=mid+1 else: #nums[left]>nums[mid] right=mid return -1 #永远不会执行 |
|---|
时间复杂度为 O(log n) ，最坏情况时间复杂度为 O(n) 。
总结
排除一些特殊案例，我们的模板大致是这样：
- 采用左右闭区间作为搜索范围;
- 确定区间划分为（
[left,mid]和[mid+1,right]）或者（[left,mid-1]和[mid,right]），即mid靠左或靠右； - 经过判断后，确定搜索范围应该缩小在左半部分（修改right）或是右半部分（修改left），注意左右的边界元素是包含在内的；
- 退出循环的条件是
left>right，确定你该在何时返回结果。
1234567891011 | def binarySearch(self, nums: List[int], target: int) -> int: left,right=0,len(nums)-1 while left<=right: mid=(left+right)//2 #或者mid=(left+right+1)//2，中位数靠左或靠右 if ... return ... #满足条件，返回 if ... left = ... #改变搜索区间 else: right = ... #改变搜索区间 return -1 #无满足条件（不一定是-1，根据题意返回） |
|---|
家庭作业
问题：在山脉数组中查找目标值。
给你一个山脉数组，你要从中找到目标值target的最小下标，即如果存在多个target取索引较小的那个，如果不存在则返回-1。
山脉数组是指存在一个最大值下标i，它的左边都是递增上升的，右边都是递增下降的，用数学描述是这样：
设山脉数组为A，那么
- 首先，A.length >= 3
- 其次，在 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个步骤解决：
- 先找到数组中的最大值的索引，将数组从这个位置一分为二；
- 从左边的递增序列中找target，找到即返回，左边的target索引肯定比右边的索引小；
- 左边没找到，就从右边的递减序列中找，找到即返回，没找到则返回-1。
步骤2和步骤3就是从有序数组中查找指定元素，这就是二分查找的最基本问题。
步骤1是要从山脉数组中找到最大值，这个问题我们例题中尚未提到过，不过也不难解决。
将数组拆分成[left,mid]和[mid+1,right]两部分，当nums[mid]<nums[mid+1]时，峰值肯定在右半部分，否则就在左半部分，而由于峰值只会有一个，所以当搜索范围缩小到left==right即只有一个元素时，这个值就是最大值。
相信通过套用这个模板，你很快就能写出代码，而这题在leetcode中已经达到了hard级别，想想应该也没有那么难，感兴趣的朋友可以试一试：
力扣入口：1095. 山脉数组中查找目标值
腾讯云开发者
