二分查找：为什么你的边界条件总是写错

1478 字

7 分钟

二分查找：为什么你的边界条件总是写错

2025-05-13

算法笔记

算法

/

二分查找

/

LeetCode

/

Python

二分查找的”入门易，精通难”#

二分查找大概是每个编程入门者最先接触的算法之一。从原理上看，它再简单不过：在一组有序数据中，每次排除一半，直到找到目标。很多人一看就”懂了”，但真到写代码的时候，循环条件是 left <= right 还是 left < right？right 更新到底是 mid 还是 mid - 1？mid 怎么算才不溢出？

我见过太多人（包括以前的我）在面试的时候，明明知道是二分，结果边界条件调半天调不出来。

根子上的问题在于：二分查找看起来是同一个算法，实际上因为区间定义的不同，衍生出了至少三种写法。你在一篇文章里学了一半，另一篇文章又学了另一半，混在一起自然出 bug。

核心理解：区间决定了边界#

二分查找的所有变体，本质上只取决于你如何定义”搜索区间”。

闭区间写法 `[left, right]`#

区间两端都包含。初始 left = 0，right = n - 1。

1
def binary_search(nums, target):
2
    left, right = 0, len(nums) - 1
3

4
    while left <= right:          # 等号不能省：left==right 时区间还有一个元素
5
        mid = left + (right - left) // 2  # 防溢出写法
6

7
        if nums[mid] == target:
8
            return mid
9
        elif nums[mid] < target:
10
            left = mid + 1         # mid 已经检查过，所以 +1
11
        else:
12
            right = mid - 1        # mid 已经检查过，所以 -1
13

14
    return -1

为什么 while left <= right？因为 [left, right] 里 left == right 时区间还有一个元素 [x, x]，得检查它。当 left > right 时空区间 [3, 2] 才意味着没找到。

为什么 left = mid + 1 和 right = mid - 1？因为 mid 已经跟 target 比较过了，确认不相等，所以下次直接跳过它。

动画中的关键点： 每一步用 mid 比较后，不相等的那半边直接灰掉（排除），剩下的区间缩小一半。括号里的 left 和 right 值看熟了，面试手写就再也不会犹豫。

开区间写法 `[left, right)`#

right 设为 n（不在区间内），循环条件变成 left < right。

1
def binary_search2(nums, target):
2
    left, right = 0, len(nums)    # right 不包含在区间内
3

4
    while left < right:           # left==right 时空区间
5
        mid = left + (right - left) // 2
6

7
        if nums[mid] == target:
8
            return mid
9
        elif nums[mid] < target:
10
            left = mid + 1
11
        else:
12
            right = mid            # mid 没被排除，但作为新区间的右边界（不包含）
13

14
    return -1

两种写法都能用，选一种吃透就行。我个人习惯闭区间写法，因为它和数组下标的直觉保持一致。

两个最容易栽的坑#

mid 越界#

很多人写 mid = (left + right) // 2。当 left + right 超过 int 上限时，就溢出了。Python 没这个问题（大整数自动扩展），但 Java、C++、Go 等语言都会炸。

统一写法：

1
mid = left + (right - left) // 2

死循环#

两个元素时 left = 0, right = 1，如果用 mid = (left + right) // 2 且更新写成 left = mid，那 mid 永远是 0，left 永远不前进——死循环。解决方法：每次更新 left 或 right 时必须跳过 mid。

实战#

704. 二分查找 #

最标准的二分查找，直接套上面的闭区间模板就能过：

1
class Solution:
2
    def search(self, nums: List[int], target: int) -> int:
3
        left, right = 0, len(nums) - 1
4
        while left <= right:
5
            mid = left + (right - left) // 2
6
            if nums[mid] == target:
7
                return mid
8
            elif nums[mid] < target:
9
                left = mid + 1
10
            else:
11
                right = mid - 1
12
        return -1

33. 搜索旋转排序数组 #

这道题是二分查找的经典变种。数组先升序排列，再从某个位置旋转了一次（比如 [0,1,2,4,5,6,7] 旋转成 [4,5,6,7,0,1,2]）。要求 O(log n) 查找 target。

关键观察： 随便切一刀 mid，左右至少有一半仍然是有序的。利用那一半判断 target 在不在里面，从而决定收缩方向。

1
class Solution:
2
    def search(self, nums: List[int], target: int) -> int:
3
        left, right = 0, len(nums) - 1
4

5
        while left <= right:
6
            mid = left + (right - left) // 2
7

8
            if nums[mid] == target:
9
                return mid
10

11
            # 左半有序
12
            if nums[left] <= nums[mid]:
13
                if nums[left] <= target < nums[mid]:
14
                    right = mid - 1   # target 在左半
15
                else:
16
                    left = mid + 1    # target 在右半
17
            # 右半有序
18
            else:
19
                if nums[mid] < target <= nums[right]:
20
                    left = mid + 1    # target 在右半
21
                else:
22
                    right = mid - 1   # target 在左半
23

24
        return -1

本质上还是二分查找，只是判断条件不再是单纯比大小，而是”先判断哪半有序，再看 target 在不在有序那半里”。

二分查找的通用框架#

把上面的思路抽象出来，二分查找的所有变种都长这样：

1
def binary_search_template(nums, target):
2
    left, right = 0, len(nums) - 1
3

4
    while left <= right:
5
        mid = left + (right - left) // 2
6

7
        # 根据题目定义"check"逻辑
8
        if check(mid, target):
9
            return mid            # 找到了
10
        elif need_go_right(mid, target):
11
            left = mid + 1        # 向右搜
12
        else:
13
            right = mid - 1       # 向左搜
14

15
    return -1  # 或 left（找插入位置等变种）

不同的题只需要改 check 和 need_go_right 两个逻辑。题做多了之后，你手里握着的不再是几十个变种的分散记忆，而是一个框架 + 两个判断。

场景	LeetCode	关键变化
标准查找	704	无
旋转数组	33	先判断有序区间
查找左边界	34	找到 target 后继续往左缩
查找右边界	34	找到 target 后继续往右缩
搜索插入位置	35	返回 left 而不是 -1
山脉数组峰值	852	check 不再比 target，而是比 nums[mid+1]
x 的平方根	69	check 是 `mid*mid <= x`
寻找峰值	162	往”上坡”方向走

千岛の摸鱼小栈

二分查找的”入门易，精通难”#

核心理解：区间决定了边界#

闭区间写法 `[left, right]`#

开区间写法 `[left, right)`#

两个最容易栽的坑#

mid 越界#

死循环#

实战#

704. 二分查找 #

33. 搜索旋转排序数组 #

二分查找的通用框架#

更多二分变种#

千岛の摸鱼小栈

二分查找的”入门易，精通难”#

核心理解：区间决定了边界#

闭区间写法 [left, right]#

开区间写法 [left, right)#

两个最容易栽的坑#

mid 越界#

死循环#

实战#

704. 二分查找#

33. 搜索旋转排序数组#

二分查找的通用框架#

更多二分变种#

闭区间写法 `[left, right]`#

开区间写法 `[left, right)`#

704. 二分查找 #

33. 搜索旋转排序数组 #