03_二分查找

二分查找

二分搜索的核心思想是利用单调性快速缩小搜索区间。

用途：$O(\log n)$ 定位目标——有序数组上找位置 / 单调判定函数上找边界。

原理：每次与区间中点比较，把搜索范围缩小一半。

本文分两大部分：

1. 有序数组上的二分查找：在已排序数组中找某个值的下标或边界；
2. 单调函数上的二分查找：在单调的布尔函数 check(x) 上找可行边界。

---

一、有序数组上的二分查找

1. 使用 bisect

bisect 函数	对应 C++	含义
bisect.bisect_left(arr, x)	lower_bound	第一个 >= x 的下标
bisect.bisect_right(arr, x)	upper_bound	第一个 > x 的下标

import bisect

arr = sorted([...])  # 先排序

# lower_bound: 第一个 >= x 的位置
pos = bisect.bisect_left(arr, x)

# upper_bound: 第一个 > x 的位置
pos = bisect.bisect_right(arr, x)

常用派生技巧：

x 的个数          = bisect_right(arr, x) - bisect_left(arr, x)
<= x 的个数       = bisect_right(arr, x)
<  x 的个数       = bisect_left(arr, x)
值域 [l, r] 内个数 = bisect_right(arr, r) - bisect_left(arr, l)
等于 x 的下标区间  = [bisect_left(arr, x), bisect_right(arr, x))

2. 手写二分

2.1 基础模板

# 查找左边界（第一个 >= target 的位置）
def lower_bound(arr, x):
    l, r = 0, len(arr)
    while l < r:
        mid = (l + r) // 2
        if arr[mid] >= x:
	        r = mid
        else:
            l = mid + 1
    return l

# 查找右边界（第一个 > target 的位置）
def upper_bound(arr, x):
    l, r = 0, len(arr)
    while l < r:
        mid = (l + r) // 2
        if arr[mid] > x:
            r = mid
        else:
            l = mid + 1
    return l

2.2 三种区间写法

手写二分有三种等价的区间约定，本质相同，只是边界表示方式不同。三者都维护同一个不变量：

l 的左侧（不含 l）都不满足条件，r 的右侧（不含 r）都满足条件。

以「找第一个 >= target 的位置」为例（即 lower_bound）。

写法一：左闭右开 [l, r)

• l 包含在区间内，r 不包含；
• 初始化 l = 0, r = n，区间 [0, n) 覆盖整个数组；
• 循环条件 l < r，因为 l == r 时区间为空；
• 命中时 r = mid（r 本身不含，所以不用 mid - 1）；
• 未命中时 l = mid + 1；
• 循环结束时 l == r，l 就是第一个满足条件的位置。

def lower_bound(arr, x):
    l, r = 0, len(arr)
    while l < r:
        mid = (l + r) // 2
        if arr[mid] >= x:
	        r = mid
        else:
            l = mid + 1
    return l

写法二：闭区间 [l, r]

• l 和 r 都包含在区间内；
• 初始化 l = 0, r = n - 1；
• 循环条件 l <= r，因为 l == r 时区间内还有一个元素 arr[l] 未检查；
• 命中时 r = mid - 1（把已检查的 mid 排除）；
• 未命中时 l = mid + 1；
• 循环结束时 l = r + 1，l 就是第一个满足条件的位置。

def lower_bound(arr, x):
    l, r = 0, len(arr) - 1
    while l <= r:
        mid = (l + r) // 2
        if arr[mid] >= x:
	        r = mid - 1
        else:
            l = mid + 1
    return l

写法三：开区间相邻 (l, r)

• l 始终指向「不满足」一侧，r 始终指向「满足」一侧；
• 初始化 l = -1, r = n，两者都是虚拟边界，不参与实际访问；
• 循环条件 l + 1 != r，即 l 与 r 相邻时结束；
• 未命中时 l = mid（mid 归入不满足侧）；
• 命中时 r = mid（mid 归入满足侧）；
• 循环结束时 r 就是第一个满足条件的位置。

def lower_bound(arr, x):
    l, r = -1, len(arr)
    while l + 1 != r:
        mid = (l + r) // 2
        if arr[mid] >= x:
	        r = mid
        else:
            l = mid
    return r

三种写法对比

对比项	写法一 [l, r)	写法二 [l, r]	写法三 (l, r)
初始化	l = 0, r = n	l = 0, r = n-1	l = -1, r = n
循环条件	l < r	l <= r	l + 1 != r
命中时更新	r = mid	r = mid - 1	r = mid
未命中时更新	l = mid + 1	l = mid + 1	l = mid
循环结束	l == r	l == r + 1	l + 1 == r
返回值	l	l	r
越界风险	无	无	无

三点注意：

1. 三种写法都能直接返回指针，不需要额外用 ans 记录候选；
2. 写法一、二返回 l，写法三返回 r，因为 r 始终指向满足侧的第一个位置；
3. 求「第一个 > x」（upper_bound）时，只需把判断条件 arr[mid] < x 改成 arr[mid] <= x，其余结构完全不变。

2.3 中点取整与溢出

关于中点写法 mid = (l + r) // 2 与 mid = l + (r - l) // 2：

• 两者在 Python 中数学上完全等价，结果相同；
• Python 整数任意精度，不存在溢出问题；
• C++ / Java 中推荐 l + (r - l) // 2，因为 l + r 可能溢出 int 范围；
• 写成 l + (r - l) // 2 在推导取整方向时更直观。

---

二、单调函数上的二分查找

1. 概念

当我们需要在单调函数上二分时，搜索对象是一个布尔函数 check(x)，满足单调性：

• 如果 check(x) = True，则 check(y) = True 对所有 y ≤ x（或 y ≥ x）

例如，对于以下函数：

check(1) = True, check(2) = True, check(3) = True, check(4) = True, check(5) = True
check(6) = False, check(7) = False, check(8) = False

则 max_ok(1, 8, check) = 5，min_ok(1, 8, check) = 1。

2. 模板

模式	函数	功能	无解时返回
找最大可行值	max_ok(l, r, check)	找最大的 x 使得 check(x)=True	l - 1
找最小可行值	min_ok(l, r, check)	找最小的 x 使得 check(x)=True	r + 1

写法一：左闭右开 + 普通取整（推荐）

把 max_ok 转成「找第一个 check = False 的位置，再减一」；min_ok 直接是标准的 lower_bound。两者都回归左闭右开模板：

def max_ok(l: int, r: int, check) -> int:
    """查找最大的 x 使得 check(x) = True"""
    l, r = l, r + 1
    while l < r:
        mid = l + (r - l) // 2
        if not check(mid):
            r = mid              # mid 为假，第一个假位置在 mid 或左边
        else:
            l = mid + 1          # mid 为真，答案在右边
    return l - 1                 # 第一个假位置 - 1 = 最后一个真位置

def min_ok(l: int, r: int, check) -> int:
    """查找最小的 x 使得 check(x) = True"""
    l, r = l, r + 1
    while l < r:
        mid = l + (r - l) // 2
        if check(mid):
            r = mid              # mid 为真，第一个真位置在 mid 或左边
        else:
            l = mid + 1          # mid 为假，答案在右边
    return l                     # 第一个真位置

优点：

• 两个分支都带 ± 1 或天然收缩，指针严格移动，不会死循环；
• mid 用普通向下取整，不需要特殊处理；

写法二：开区间相邻 + 特殊取整

max_ok 原本是找最后一个 check(x) = True 的位置，等价于：找第一个 check(x) = False 的位置，再减一。

from typing import Callable

def max_ok(l: int, r: int, check: Callable[[int], bool]) -> int:
    """查找最大的 x 使得 check(x) = True"""
    l -= 1
    while l < r:
        mid = l + (r - l + 1) // 2  # 向上取整
        if check(mid):
            l = mid
        else:
            r = mid - 1
    return l

def min_ok(l: int, r: int, check: Callable[[int], bool]) -> int:
    """查找最小的 x 使得 check(x) = True"""
    r += 1
    while l < r:
        mid = l + (r - l) // 2  # 向下取整
        if check(mid):
            r = mid
        else:
            l = mid + 1
    return l

为什么 max_ok 要 l -= 1，min_ok 要 r += 1？

• max_ok 若整个区间无解，应返回 original_l - 1。把 l 设为 original_l - 1，让它成为“无解标记”，循环中若从未命中，直接返回 l 即可。
• min_ok 对称，把 r 设为 original_r + 1，无解时返回 r + 1。

为什么一个用向上取整，一个用向下取整？

• max_ok 中有 l = mid，若 mid == l 会死循环。向上取整让 mid 偏向 r，避免 mid == l。
• min_ok 中有 r = mid，若 mid == r 会死循环。向下取整让 mid 偏向 l，避免 mid == r。

规则：谁被赋值为 mid，谁就不能原地踏步；取整方向要让 mid 偏向不会原地踏步的那一侧。

3. 中点取整方向

向下取整（标准）

[ = ]

mid = (l + r) // 2
# 或等价地
mid = l + (r - l) // 2

向上取整

[ = ]

mid = (l + r + 1) // 2
# 或等价地
mid = l + (r - l + 1) // 2

原理：(a/b = (a + b - 1) // b)，当 (b = 2) 时即 (a + 1) // 2。

4. 常见错误

错误 1：mid 取整方向错误

当 l = 0, r = 1 时，若在 l = mid 的模板里使用向下取整：

mid = (l + r) // 2  # = 0，l = mid = 0，无限循环

修复：

• 找最大可行值（向右收缩，l = mid）→ 向上取整；
• 找最小可行值（向左收缩，r = mid）→ 向下取整；
• 或者改用写法二（左闭右开 + mid ± 1），从根上避免这个问题。

错误 2：负数边界

mid = (l + r) // 2 对负数在 Python 中仍然是向下取整（因为 Python 的 // 就是向下取整），不会出错。但在 C++ / Java 中整数除法是向零截断，对负数的行为与 Python 不同，需改用 l + (r - l) // 2。