1、普通查找：闭区间写法#

如果目标是在有序数组中查找一个确定的值，可以使用闭区间 [left, right]：

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

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

7
        if nums[mid] == target:
8
            return mid
9
        elif nums[mid] < target:
10
            left = mid + 1
11
        else:
12
            right = mid - 1
13

14
    return -1

这里 right 一开始是最后一个有效下标，所以循环条件是 left <= right。当 left == right 时，区间里还剩一个元素，需要继续检查。

2、为什么要加一减一#

闭区间写法里，mid 已经被检查过了。如果 nums[mid] < target，说明 mid 以及它左边都不可能是答案，所以下一次从 mid + 1 开始。

同理，如果 nums[mid] > target，下一次应该到 mid - 1：

1
left = mid + 1
2
right = mid - 1

如果这里写成 left = mid 或 right = mid，在某些情况下区间不会缩小，就可能出现死循环。

3、查找第一个满足条件的位置#

实际刷题时，更常见的是找边界：比如第一个大于等于 target 的位置。这个时候我更喜欢左闭右开区间 [left, right)：

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

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

7
        if nums[mid] >= target:
8
            right = mid
9
        else:
10
            left = mid + 1
11

12
    return left

这段代码返回的是第一个满足 nums[i] >= target 的下标。如果所有元素都小于 target，返回值会是 len(nums)。

4、用例子走一遍#

假设：

1
nums = [1, 3, 3, 5, 8]
2
target = 3

我们想找第一个大于等于 3 的位置，也就是下标 1。

初始区间是 [0, 5)，mid = 2，nums[2] = 3，满足条件，所以答案可能是 2，也可能在左边，于是 right = 2。

接着区间变成 [0, 2)，mid = 1，nums[1] = 3，继续满足条件，right = 1。

再然后区间是 [0, 1)，mid = 0，nums[0] = 1，不满足条件，left = 1。

最后 left == right == 1，返回 1。

5、把条件抽象出来#

很多二分题都可以改写成“找第一个满足条件的位置”：

1
def first_true(n, check):
2
    left, right = 0, n
3

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

7
        if check(mid):
8
            right = mid
9
        else:
10
            left = mid + 1
11

12
    return left

只要 check(i) 的结果从 False 到 True 只变化一次，这个模板就能使用。

例如在答案区间里找最小可行值时，check(mid) 就是“当前答案是否可行”。

小结#

我现在会把二分查找分成两类记：

• 找具体值：闭区间 [left, right]，循环条件 left <= right。
• 找边界位置：左闭右开 [left, right)，循环条件 left < right。

最重要的是不要混用规则。只要区间定义清楚，mid 是否已经排除、返回 left 还是 -1，都会变得更容易判断。