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

1
2
3
4
5
6
7
8
9
while left<=right:            
    mid=(left+right)//2   # 中间数在左范围
    if left==right:  # 只剩最后一个元素，返回结果
        return ...
    if ...:          # 判断mid是否满足条件，如果满足继续搜索左范围
        right=mid
    else:            # 如果不满足则搜索右范围
        left=mid+1
return -1 #永远不会执行

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

1
2
3
4
5
6
7
8
9
while left<=right:            
    mid=(left+right+1)//2   # 中间数在右范围
    if left==right:  # 只剩最后一个元素，返回结果
        return ...
    if ...:          # 判断mid是否满足条件，如果满足继续搜索右范围
        left=mid
    else:            # 如果不满足则搜索左范围
        right=mid-1
return -1 #永远不会执行

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

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

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

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

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，这里会有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种结果合并返回了，这是值得注意的地方。
而套用模板，你只需思考每轮结束后，下一轮应该搜索的区间是什么，以及什么时候该返回结果，最后再想想有没有重复的判断可以抽离出来的（这一步实际上可有可无，毕竟除了让代码变少，对时间复杂度没有什么影响）。

Python库中的二分查找

在python的bisect库中有2个函数使用二分查找来找到目标元素插入的索引位置，其中left和right表示当元素相同时，是插入到最左侧的索引还是最右侧的索引：

1
2
3
import bisect
bisect.bisect_left([1,2],1)  # 不插入值，返回左侧的索引，输出：0
bisect.bisect_right([1,2],1) # 不插入值，返回右侧的索引，输出：1

以下是模拟的代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def bisect_left(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-1                 #相等时，搜索[left,mid-1]
        elif nums[mid]<target:
            left=mid+1          #搜索[mid+1,right]
        else:
            right=mid-1         #搜索[left,mid-1]
    return left

def bisect_right(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:
            left=mid+1                #相等时，搜索[mid+1,right]
        elif nums[mid]<target:
            left=mid+1          #搜索[mid+1,right]
        else:
            right=mid-1         #搜索[left,mid-1]
    return left

可以看到，2个函数的代码几乎完全一致，都是将mid划分在左区间，同时返回结果为左端点索引，唯一的区别是当nums[mid]==target相等时，是搜索左区间[left,mid-1]还是右区间[mid+1,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  #永远不会执行

可以发现当left和right相等时，循环内部直接返回了，所以循环外的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. 山脉数组中查找目标值