数据结构+算法=程序
程序+设计模式=框架

0%

二分查找的通用模板

二分查找适用于对于有序数组的精确查找,例如从一个有序数组中找到指定元素的索引,可将时间复杂度从普通枚举的$ 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排除在外。

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

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

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

1
2
3
4
5
6
7
8
9
10
11
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是可以省略的,简单调整下:

1
2
3
4
5
6
7
8
9
10
11
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纳入了重复搜索区间,所以当只剩一个元素的时候一定要返回,否则会无法退出循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
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

1
2
3
4
5
6
7
8
9
10
11
12
13
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段优化后的代码有什么不同:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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

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
而套用模板,你只需思考每轮结束后,下一轮应该搜索的区间是什么,以及什么时候该返回结果,最后再想想有没有重复的判断可以抽离出来的(这一步实际上可有可无,毕竟除了让代码变少,对时间复杂度没有什么影响)。
接下来进阶看看更难的例子。

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

旋转排序数组是指有序数组在某一个点进行了旋转而得到数组,例如[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在这个部分,则搜索另一个部分。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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右移一位,相当于排除一个元素,再继续搜索。
相较例题四,只需把相等的情况抽离出来单独判断即可:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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) $,由于只是对相同元素的情况做了特殊处理,所以该代码其实完全适用于例题四。

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

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

  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。这也是二分查找的核心思想,每轮将搜索范围缩小一半。

1
2
3
4
5
6
7
8
9
10
11
12
13
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 #永远不会执行

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

1
2
3
4
5
6
7
8
9
10
11
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]情况单独抽离出来:

  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,不变
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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) $。

总结

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

  1. 采用左右闭区间作为搜索范围;
  2. 确定区间划分为([left,mid][mid+1,right])或者([left,mid-1][mid,right]),即mid靠左或靠右;
  3. 经过判断后,确定搜索范围应该缩小在左半部分(修改right)或是右半部分(修改left),注意左右的边界元素是包含在内的;
  4. 退出循环的条件是left>right,确定你该在何时返回结果。
1
2
3
4
5
6
7
8
9
10
11
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,那么

  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. 山脉数组中查找目标值