第 44 章　二分

本章配套 17 道例题，见 §例题。

二分是用 \(O(\log n)\) 次判定，在一个有序（或单调）的空间里定位答案。 按用途可以分成两类，这个分法非常好用：

类型	空间	判定	典型
二分查找	有序数组的下标	a[mid] 与目标比较	找第一个 \(\ge x\) 的位置
二分答案	答案的值域	check(mid) 是否可行	「最大值最小」「最小值最大」

两者的代码骨架完全一样，区别只在「拿什么当判定」。

Python 选手的第一原则：能用 bisect 就绝不手写。手写二分的边界错误是竞赛里 最难查的 bug 之一，而 bisect 是 C 实现且经过千锤百炼。

---

1　bisect：优先选项

from bisect import bisect_left, bisect_right, insort

bisect_left(a, x)      # 第一个 >= x 的下标（等于 x 的元素若存在，落在返回值右边）
bisect_right(a, x)     # 第一个 >  x 的下标（等于 x 的元素若存在，落在返回值左边）
insort(a, x)           # 保持有序地插入：定位 O(log n)，但列表搬移是 O(n)

所有常见需求都能由这两个函数拼出来，这张表建议直接背：

需求（a 已升序）	写法
第一个 \(\ge x\) 的下标	bisect_left(a, x)
第一个 \(> x\) 的下标	bisect_right(a, x)
最后一个 \(< x\) 的下标	bisect_left(a, x) - 1
最后一个 \(\le x\) 的下标	bisect_right(a, x) - 1
\(x\) 出现的次数	bisect_right(a, x) - bisect_left(a, x)
值在 \([l, r]\) 内的元素个数	bisect_right(a, r) - bisect_left(a, l)
\(x\) 是否存在	i = bisect_left(a, x); i < len(a) and a[i] == x

三个额外能力：

bisect_left(a, x, lo, hi)               # 限定搜索区间 [lo, hi)：左闭右开，比切片省一次 O(n) 复制
bisect_left(keys, x)                    # 3.10+ 支持 key= 参数；3.9 需自建 keys 数组

Python 3.9 的 bisect 没有 key 参数（3.10 才加）。 要按某个字段二分时，3.9 的做法是先抽出一个纯关键字数组：

keys = [t[0] for t in items]          # 提前把关键字抽出来
i = bisect_left(keys, x)

全书按 3.9 编写，一律用这种写法。

降序数组怎么办

bisect 只认升序。降序数组有两种处理：

# 方案一（推荐）：存相反数，转成升序
a_neg = [-v for v in a]                 # 取负把降序翻成升序，大小关系整体反转
i = bisect_left(a_neg, -x)              # 查找目标也要取负，才对应原来的那个位置

# 方案二：手写二分（见 44.2）

---

2　整数二分的四种边界写法

必须手写时（比如二分答案），把下面四个模板抄进代码即可。 它们的区别只在「循环条件」「mid 取法」「谁 = mid」三处，一定要成套记忆。

写法一：找第一个满足 check 的位置（下界）

def lower(lo, hi, check):
    """在 [lo, hi] 上找最小的 x 使 check(x) 为真。
    要求 check 单调：False...False True...True。若全 False 返回 hi+1。"""
    hi += 1                              # 哨兵：搜索范围扩成 [lo, hi+1]，多出的那一格代表「不存在」
    # 循环不变量：答案一定落在闭区间 [lo, hi] 里
    # （lo 左边的都已确认为 False，hi 右边的即使为 True 也不是最小的）
    while lo < hi:                       # lo == hi 时区间只剩一个数，它必然就是答案
        mid = (lo + hi) // 2             # 向下取整。由 lo < hi 可得 lo <= mid < hi
        if check(mid):
            hi = mid                     # mid 满足条件，它自己可能就是最小的，必须留在区间里
        else:
            lo = mid + 1                 # mid 不满足，比它小的更不满足，答案只可能在右半边
    # 不死循环的理由：hi = mid 时因 mid < hi 而右端严格左移，lo = mid+1 时左端严格右移，
    # 两支都让区间长度至少减 1，所以最多 log2(hi-lo+1) 轮就收敛
    return lo

写法二：找最后一个满足 check 的位置（上界）

def upper(lo, hi, check):
    """在 [lo, hi] 上找最大的 x 使 check(x) 为真。
    要求 check 单调：True...True False...False。若全 False 返回 lo-1。"""
    lo -= 1                              # 哨兵：搜索范围扩成 [lo-1, hi]，多出的那一格代表「不存在」
    # 循环不变量：答案一定落在闭区间 [lo, hi] 里
    while lo < hi:                       # lo == hi 时区间只剩一个数，它必然就是答案
        mid = (lo + hi + 1) // 2         # 注意 +1，向上取整！由 lo < hi 可得 lo < mid <= hi
        if check(mid):
            lo = mid                     # mid 满足条件，它自己可能就是最大的，必须留在区间里
        else:
            hi = mid - 1                 # mid 不满足，比它大的更不满足，答案只可能在左半边
    # 上取整是这里唯一的保命符：它保证 mid > lo，于是 lo = mid 也让左端严格右移。
    # 若用下取整，hi == lo+1 且 check(lo) 为真时 mid == lo，区间纹丝不动，直接死循环
    return lo

+1 是写法二的生命线。若写成 (lo + hi) // 2，当 hi = lo + 1 且 check(lo) 为真时，mid = lo，于是 lo = mid = lo——区间不缩小，死循环。

口诀：谁取 mid 谁就要防死循环。lo = mid 就要 mid 上取整。

写法三：闭区间 + 显式返回（最接近 C++ 教材）

def binary_search(a, target):
    """在升序数组里找 target，返回下标；不存在返回 -1。"""
    lo, hi = 0, len(a) - 1               # 搜索范围是闭区间 [lo, hi]，两端都还没被检查过
    # 循环不变量：target 若存在，一定落在 a[lo..hi] 里
    while lo <= hi:                      # 注意是 <=：lo == hi 时区间还剩一个元素，仍要查
        mid = (lo + hi) // 2
        if a[mid] == target:
            return mid                   # 命中即返回，不必等区间收敛
        if a[mid] < target:
            lo = mid + 1                 # a[mid] 偏小，mid 及其左边全部排除
        else:
            hi = mid - 1                 # a[mid] 偏大，mid 及其右边全部排除
    # 两支都把 mid 本身踢出区间，所以区间每轮至少缩短 1，不会死循环
    return -1                            # 循环因 lo > hi（区间为空）退出，说明不存在

写法四：l/r 各退一步（不需要哨兵，靠不变量）

def split_point(lo, hi, check):
    """维持不变量：check(lo) 恒真、check(hi) 恒假。返回最后一个真的位置。
    调用前必须保证 check(lo) 为真、check(hi) 为假。"""
    while hi - lo > 1:                   # 收敛到 lo 与 hi 相邻为止，分界线就夹在两者之间
        mid = (lo + hi) // 2             # 由 hi - lo >= 2 可得 lo < mid < hi，赋给谁都能缩短区间
        if check(mid):
            lo = mid                     # mid 为真 -> 把「真」的右边界推到 mid
        else:
            hi = mid                     # mid 为假 -> 把「假」的左边界拉到 mid
    # 因为 mid 严格落在两端之间，两支都让区间至少缩短 1，不存在下取整式的死循环
    return lo                            # 不变量保证：lo 是最后一个真，hi 是第一个假

四种写法的对照：

写法	循环条件	mid	收敛后	适用
一（下界）	lo < hi	下取整	lo == hi	最小的可行解
二（上界）	lo < hi	上取整	lo == hi	最大的可行解
三（闭区间）	lo <= hi	下取整	lo > hi	精确查找
四（不变量）	hi - lo > 1	下取整	相邻	分界点，两边都要

建议只记住写法一和写法二，其余用 bisect。 两者的记忆锚点： 求最小 → hi = mid，mid 下取整；求最大 → lo = mid，mid 上取整。

Python 里不用担心的两件事

mid = (lo + hi) // 2          # ✅ Python 整数无上限，lo + hi 再大也不会溢出
mid = lo + (hi - lo) // 2     # C++ 里的防溢出写法；两式在 lo <= hi 时结果相同，Python 不需要

但必须用 // 而不是 /——/ 返回 float，当下标会直接 TypeError， 当值域二分时会悄悄丢精度。见 运算符与位运算。

---

3　二分答案

这类题可以精准地总结成一句：

通常来说，二分答案题目为下列两种中的一种： ① 给定评价函数，求其最小 / 最大值；② 给定条件，在满足条件的同时使代价最小。 计算函数或判断条件很慢，或者值域太大不能一一枚举。

题面里的信号词：

出现这些字眼	往二分答案想
「最大值最小」/「最小值最大」	⭐⭐⭐ 几乎必是
「最少需要多少 ×× 才能……」	⭐⭐
「使得所有 ×× 都不超过 \(k\)，求最小的 \(k\)」	⭐⭐⭐
「第 \(k\) 小的数是多少」	⭐⭐（二分值 + 数有多少个 \(\le\) 它）

标准骨架：

def solve():
    def check(x):
        """答案取 x 时是否可行。必须对 x 单调：一旦某个 x 可行，更大的 x 也必须可行。"""
        ...
        return True

    lo, hi = 0, UPPER                    # 上界要给足，保证 check(hi) 为真，否则返回值没有意义
    # 与 44.2 写法一同构：求最小可行解 -> mid 下取整、可行时 hi = mid
    while lo < hi:
        mid = (lo + hi) // 2
        if check(mid):
            hi = mid                     # mid 可行，它自己可能就是最小的，保留
        else:
            lo = mid + 1                 # mid 不可行，答案只可能更大
    return lo                            # 收敛到 lo == hi，即最小的可行答案

两步走：① 观察单调性，找到需要计算的条件；② 二分并验证条件。 难点永远在 ①②，而不在二分本身。

check 常用的实现手段	例子
贪心	跳石头、魔法染色（BISHI88）
前缀和 / 差分	NOIp 2012 借教室
DP	划分成 \(k\) 段使最大段和最小
数据结构	NOIp 2015 运输计划（树上差分）
直接求和	扑克牌（BISHI87）

另一句提醒：不是要死磕在二分法上。如果验证方法足够优秀， 完全可以抛弃二分，直接使用优秀的方法求得答案。 比如 BISHI89 可以二分，也可以直接双指针；BISHI118 更是排序后一遍扫完。 二分是保底手段，不是唯一手段。

---

4　实数二分：固定迭代次数，不要用 while r - l > eps

C++ 里常见的写法是 while (right - left > precision)。 在竞赛里更推荐固定迭代次数：

lo, hi = 0.0, 1e18                       # 答案始终夹在 lo 与 hi 之间
for _ in range(100):                     # 固定 100 次，绝不死循环
    mid = (lo + hi) / 2                  # 实数域用 / 而不是 //，这里不需要取整
    if check(mid):
        hi = mid                         # mid 可行 -> 答案不超过 mid（求最小可行值）
    else:
        lo = mid                         # 实数没有「下一个数」，所以是 lo = mid 而非 mid + 1
print("%.6f" % lo)                       # 收敛后 lo 与 hi 之差远小于精度要求，输出哪个都行

写法	风险
while hi - lo > 1e-9	当 lo、hi 很大时（如 \(10^{18}\)），浮点精度不足以让差值降到 \(10^{-9}\)，死循环
for _ in range(100)	每次区间减半，100 次后区间长度是初始的 \(2^{-100} \approx 10^{-30}\)，远超任何精度要求

迭代次数怎么选：区间初长 \(L\)，要求精度 \(\epsilon\)，则需要 \(\log_2(L/\epsilon)\) 次。 \(L = 10^{18}\)、\(\epsilon = 10^{-9}\) 时约 90 次，取 100 稳妥。 double 只有 53 位尾数，超过 100 次迭代纯属浪费（区间已经小到浮点无法表示）。

实数二分的另一条铁律：能转成整数二分就转。 比如「求最小半径 \(r\)」的题，二分 \(r^2\)（整数）比二分 \(r\)（实数）更精确， 最后再开方输出。BISHI86 就是这种情况。

---

5　三分：单峰函数求极值

二分要求单调，三分只要求单峰（先增后减，或先减后增）。

def ternary_max(lo, hi, f):
    """求单峰函数 f 在 [lo, hi] 上的最大值点（实数域）。"""
    for _ in range(200):                 # 每次区间缩到 2/3，200 次足够
        m1 = lo + (hi - lo) / 3          # 两个三等分点，恒有 m1 < m2
        m2 = hi - (hi - lo) / 3
        if f(m1) < f(m2):
            lo = m1                      # m1 处更低，峰只可能在 m1 右边，砍掉 [lo, m1)
        else:
            hi = m2                      # 否则峰在 m2 左边，砍掉 (m2, hi]
    return (lo + hi) / 2                 # 区间已经极短，取中点当答案


def ternary_max_int(lo, hi, f):
    """整数域三分：区间缩到只剩两三个数时暴力比较。"""
    while hi - lo > 2:                   # 留 3 个数就收手：再缩下去取整会让区间不再变小
        m1 = lo + (hi - lo) // 3
        m2 = hi - (hi - lo) // 3
        if f(m1) < f(m2):
            lo = m1 + 1                  # m1 已确定不是峰值点，可以连它一起排除
        else:
            hi = m2
    return max(range(lo, hi + 1), key=f)   # 最后 2–3 个候选直接比，顺带绕开平台段的坑

	二分	三分
前提	单调	单峰
每次区间缩到	\(1/2\)	\(2/3\)
迭代次数（同精度）	\(\log_2\)	\(\log_{1.5}\)，约 1.7 倍
严格性要求	无	必须严格单峰，有平台段会挂

有「平台段」（相邻值相等）时三分不可靠。整数域三分尤其容易踩， 稳妥做法是最后留 3–5 个候选点暴力比较，就像上面的 ternary_max_int。

---

6　二分的「隐身」形态

还有一串「其实也是二分」的东西，值得记住：

形态	说明	章节
二叉搜索树 / 线段树	每次砍掉一半区间	线段树
倍增	从大到小试跳，本质是二进制拆分	倍增
LIS 的 \(O(n\log n)\) 解法	在「各长度的最小结尾」数组上二分	线性DP
高精度除法	二分商	高精度与大整数
整体二分 / CDQ	对答案分治	整体二分 / CDQ 分治
分数规划	二分比值再判定	—

---

7　例题

题号	题名	难度	题解
BISHI85	【模板】整数域二分	简单	题解
BISHI86	圆覆盖	中等	题解
BISHI87	[CQOI2010]扑克牌	中等	题解
BISHI88	小苯的魔法染色	中等	题解
BISHI89	山峰数组计数	中等	题解
BISHI91	拼接木棍	中等	题解
BM17	二分查找-I	简单	题解
BM18	二维数组中的查找	中等	题解
BM19	寻找峰值	中等	题解
BM21	旋转数组的最小数字	简单	题解
LC4	寻找两个正序数组的中位数	困难	题解
LC33	搜索旋转排序数组	中等	题解
LC34	在排序数组中查找元素的第一个和最后一个位置	中等	题解
LC35	搜索插入位置	简单	题解
LC74	搜索二维矩阵	中等	题解
LC153	寻找旋转排序数组中的最小值	中等	题解
LC240	搜索二维矩阵 II	中等	题解

BISHI85　【模板】整数域二分（简单）

\(n, q \le 2\times10^5\)，\(|a_i| \le 10^9\)。每次询问「数组中值在 \([l, r]\) 内的元素个数」。 题面见 原题。

排序 + 两次 bisect 相减，§1 那张表的直接应用：

import sys
from bisect import bisect_left, bisect_right


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); q = int(data[1])
    a = sorted(map(int, data[2:2 + n]))               # bisect 的前提：有序
    qs = list(map(int, data[2 + n:2 + n + 2 * q]))    # 每个询问占 2 个 token
    out = []
    ap = out.append
    for i in range(0, 2 * q, 2):
        l = qs[i]; r = qs[i + 1]
        # bisect_right(a, r) 是「第一个 > r 的下标」= 值 <= r 的元素个数
        # bisect_left(a, l) 是「第一个 >= l 的下标」= 值 < l 的元素个数
        # 两者相减即闭区间 [l, r] 内的元素个数
        c = bisect_right(a, r) - bisect_left(a, l)    # <= r 的个数 - < l 的个数
        ap(c if c > 0 else 0)                         # 题面未保证 l <= r，负数时取 0 兜底
    sys.stdout.write("\n".join(map(str, out)) + "\n")


main()

四个要点：

• 左边界用 bisect_left、右边界用 bisect_right，这样两端都是闭区间。 两个都用 bisect_left 会漏掉等于 \(r\) 的元素——这是本题唯一的考点。
• 题面只说 \(-10^9 \le l, r \le 10^9\)，没保证 \(l \le r\)。 真出现 \(l > r\) 时两式相减会是负数，所以加一句 if c > 0 else 0 兜底。 读数据范围时留意「有没有保证 \(l \le r\)」是一个好习惯。
• 手写二分在这里毫无意义：\(q = 2\times10^5\) 次查询，bisect 全在 C 层， 手写要多出 \(2\times10^5 \times 18\) 次 Python 循环。
• 若题目改成「带修改」，就该上树状数组了，见 树状数组。

BISHI87　[CQOI2010] 扑克牌（中等）

\(n\ (\le 50)\) 种牌，第 \(i\) 种有 \(c_i\) 张，另有 \(m\) 张 Joker。 一套牌 = \(n\) 种各一张，或 Joker + 其余 \(n-1\) 种各一张。求最多组几套。 \(c_i, m \le 5\times10^8\)。 题面见 原题。

二分答案的教科书例题：直接构造很难，但「能不能组出 \(t\) 套」很好判。

固定 \(t\)，考察可行性：

• 每套牌里第 \(i\) 种最多用 1 张，所以第 \(i\) 种牌总共最多贡献 \(\min(c_i, t)\) 张；
• 每套牌最多用 1 张 Joker，所以 Joker 最多贡献 \(\min(m, t)\) 张；
• 总共需要 \(n \cdot t\) 张牌。

\[\text{可行} \iff \sum_{i} \min(c_i, t) + \min(m, t) \ge n \cdot t\]

单调性：\(t\) 增大时左边最多线性增长（斜率 \(\le n\)），右边斜率恰好 \(n\)， 而每种牌迟早会被 \(\min\) 卡住，所以差值单调不增——可行性关于 \(t\) 单调。

import sys


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); m = int(data[1])
    c = list(map(int, data[2:2 + n]))

    def ok(t):
        """能否凑出 t 套牌。t 增大时左边最多线性增长、右边斜率恰为 n，故可行性单调。"""
        if t == 0:
            return True                            # 一套都不组永远可行，作为二分的下界锚点
        s = 0
        for x in c:
            s += x if x < t else t                 # 每种牌在 t 套里最多用 t 张，多的用不上
        return s + (m if m < t else t) >= n * t    # 可用牌数 >= 需求 n*t

    lo, hi = 0, (sum(c) + m) // n + 1              # 牌总数除以每套张数再 +1，这个 hi 一定不可行
    # 求「最大的可行 t」= 44.2 写法二：mid 必须上取整，否则 hi == lo+1 时死循环
    while lo < hi:
        mid = (lo + hi + 1) // 2                   # 求「最大的可行 t」-> mid 上取整
        if ok(mid):
            lo = mid                               # mid 可行，它自己可能就是最大值，保留
        else:
            hi = mid - 1                           # mid 不可行，更大的更不可行
    print(lo)


main()

• 用的是 §2 的写法二（求最大可行解），所以 mid 必须 (lo + hi + 1) // 2。 写成下取整会在 hi = lo + 1 时死循环。
• 上界取 \(\lfloor(\sum c_i + m)/n\rfloor + 1\)：牌总数除以每套需要的张数， 再 \(+1\) 确保它不可行。上界给宽一点不会变慢（只多一两次迭代），给窄了会 WA。
• min 用条件表达式手写：x if x < t else t 比 min(x, t) 略快， 因为省掉一次函数调用。\(n \le 50\) 时无所谓，但这个习惯在热循环里值钱。

BISHI88　小苯的魔法染色（中等）

长为 \(n\) 的 W/R 串，最多施法 \(m\) 次，每次把一个长度 \(\le k\) 的区间全染红。 求能把所有 W 染红的最小 \(k\)。\(m \le n \le 2\times10^5\)。 题面见 原题。

题面直接写着「求最小的 \(k\)」，且 \(k\) 越大越容易做到——单调性是显然的，二分答案。

check(k) 用贪心：从左往右扫所有 W，遇到没被覆盖的就在这里开一个长度为 \(k\) 的区间 （起点就放在这个 W 上，能覆盖到最右）。这样用的区间数最少。

import sys


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); m = int(data[1])
    s = data[2]
    pos = [i for i, ch in enumerate(s) if ch == 87]     # 'W' 的 ASCII 码是 87

    if not pos:                                          # 没有白格，一次都不用施法
        print(0)
        return

    def ok(k):
        """长度上限取 k 时，m 次施法够不够。k 越大越容易达成，所以可行性对 k 单调。"""
        cnt = 0
        cover = -1                                       # 已覆盖到的最右下标，-1 表示还没覆盖任何格
        for i in pos:
            if i > cover:                                # 这个 W 还露在外面，必须新开一个区间
                cnt += 1
                if cnt > m:
                    return False                         # 已超预算，后面不用再看了
                cover = i + k - 1                        # 起点压在这个 W 上，右端因此最远
        return True

    lo, hi = 1, n                                        # 长度至少 1，至多 n（一次盖全串）
    while lo < hi:                                       # 求最小可行 k -> 写法一
        mid = (lo + hi) // 2                             # 下取整，配合 hi = mid 不会死循环
        if ok(mid):
            hi = mid                                     # mid 够用，更小的还可能够
        else:
            lo = mid + 1                                 # mid 不够用，答案只可能更大
    print(lo)


main()

• 贪心的正确性：区间起点放在当前最左未覆盖的 W 上是最优的—— 再往左浪费长度，再往右就盖不住这个 W。这是标准的区间覆盖贪心，见 贪心。
• 只遍历 W 的位置而不是整个串：check 从 \(O(n)\) 降到 \(O(|W|)\)， 总复杂度 \(O(|W|\log n)\)。
• cnt > m 立刻 return False：这个剪枝在 \(k\) 很小时能省掉绝大部分工作。
• s 是 bytes，逐字节比较的是整数（'W' 是 87）。 写 ch == 'W' 会永远为假——这是 buffer.read() 最常见的坑，见 输入输出处理。
• 全 R 时答案是 0，不是 1。 题面写着「输出一个正整数」， 但实测数据里存在全 R 的测试点，期望输出是 \(0\)——一次都不用施法。 这类「输出描述与真实数据不符」并不罕见： 边界情形以数据为准，题面的措辞不能当成担保。 更麻烦的是这种错法只挂在一个分支上，二分主体完全正确， 很容易误判成二分写错而去反复改主循环。

BISHI89　山峰数组计数（中等）

把长为 \(n\) 的正整数数组切成三段（\(b_1, b_2, b_3\) 为三段和）， 求满足 \(b_1 < b_2 > b_3\) 的切法数。\(n \le 2\times10^5\)，\(P_i \ge 1\)。 题面见 原题。

设前缀和 \(S\)，切点为 \(i < j\)，则 \(b_1 = S_i\)、\(b_2 = S_j - S_i\)、\(b_3 = S_n - S_j\)。 两个条件都能整理成「\(S_j\) 大于某个只与 \(i\) 有关的量」：

\[\begin{aligned} b_1 < b_2 &\iff S_i < S_j - S_i \iff S_j > 2S_i\\ b_2 > b_3 &\iff S_j - S_i > S_n - S_j \iff 2S_j > S_n + S_i \end{aligned}\]

因为 \(P_i \ge 1\)，前缀和 \(S\) 严格递增——这就给了二分的前提。 枚举 \(i\)，二分出最小的合法 \(j\)，其后的 \(j\) 全部合法，一次算完：

import sys
from bisect import bisect_left
from itertools import accumulate


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    # 前面补 0，下标偏移一位：pre[i] = P1 + .. + Pi，pre[0] = 0
    pre = [0] + list(accumulate(map(int, data[1:1 + n])))    # pre[i] = P1+..+Pi
    S = pre[n]                                # 全部元素之和

    ans = 0
    for i in range(1, n - 1):                 # i 是第一个切点，右边至少要留下 j 和第三段
        x = pre[i]
        low = 2 * x + 1                       # S_j > 2 S_i，整数化成 >= 2S_i + 1
        low2 = (S + x) // 2 + 1               # 2 S_j > S + S_i -> S_j >= ⌊(S+S_i)/2⌋+1
        if low2 > low:                        # 两个下界取更严的那个
            low = low2
        # P_i >= 1 使 pre 严格递增，才有资格上 bisect；三、四参数限定 [i+1, n)，避开 O(n) 切片
        j = bisect_left(pre, low, i + 1, n)   # 在 pre[i+1 .. n-1] 里找第一个 >= low
        if j <= n - 1:
            ans += n - j                      # pre 递增，j 之后的 j 全部满足，一次性累加
    print(ans)


main()

三个要点：

• 严格不等式的整数化：\(S_j > 2S_i\) 等价于 \(S_j \ge 2S_i + 1\)； \(2S_j > S + S_i\) 等价于 \(S_j \ge \lfloor (S+S_i)/2 \rfloor + 1\)。 在整数域上，把「\(>\)」变成「\(\ge\) 某个整数」再交给 bisect_left， 是避免边界错误的最稳做法。 千万别用浮点除法。
• bisect_left(pre, low, i + 1, n) 的三、四参数限定了搜索区间 \([i+1, n)\)， 正好对应 \(j\) 的合法范围 \(i < j < n\)。这比切片 pre[i+1:n] 好——切片是 \(O(n)\) 复制。
• 这题也可以用双指针（两个阈值都随 \(i\) 单调递增），\(O(n)\) 且更快。 这正是 §3 末尾那句提醒的实例：二分是保底，不是唯一。

BISHI86　圆覆盖（中等）

平面上 \(n \le 10^5\) 个带权点，以原点为圆心放一个圆， 求使被覆盖点权值和 \(\ge S\) 的最小半径；无解输出 \(-1\)。 相对误差 \(10^{-6}\) 内算对。 题面见 原题。

这题的正解是「二分的退化形态」：把点按到原点距离的平方 \(d_i = x_i^2 + y_i^2\) （整数！）排序，求权值前缀和，第一个前缀和 \(\ge S\) 的位置就是答案， 半径 \(= \sqrt{d}\)。

# [片段] 本题输出实数、官方为 special judge，未接入本地自动校验
import sys
from itertools import accumulate
from math import isqrt


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); S = int(data[1])
    pts = []
    for i in range(n):
        # 每个点占 3 个 token（x, y, v），第 i 个点从下标 2 + 3i 开始
        x = int(data[2 + 3 * i]); y = int(data[3 + 3 * i]); v = int(data[4 + 3 * i])
        pts.append((x * x + y * y, v))        # 距离的平方，整数，不丢精度
    pts.sort()                                # 按距离平方升序 = 按半径升序（平方在非负数上保序）
    tot = 0
    for d, v in pts:
        tot += v                              # 半径扩到 d 时被覆盖的权值和
        if tot >= S:
            print("%.6f" % (d ** 0.5))        # 首次达标的位置就是答案，最后一步才开方
            return
    print(-1)                                 # 全部点都覆盖仍不够，无解


main()

三条本章要强调的经验：

• 能用整数就别用浮点：比较距离时用 \(d = x^2+y^2\)，只在最后一步开方。 \(|x|, |y| \le 10^9\) 时 \(d\) 可到 \(2\times10^{18}\)，C++ 要 long long 且要小心中间溢出， Python 的 int 无上限，直接算。
• 权值和 \(S \le 10^{14}\)，同样超 32 位，Python 无感。
• 半径本身要不要二分？不需要。 答案一定取在某个点的距离上（半径再小就少覆盖一个点）， 所以排序 + 前缀和一遍扫完，\(O(n\log n)\)，比「二分半径 + 每次 \(O(n)\) 统计」的 \(O(n\log V)\) 更快也更精确。这就是上面说的「验证方法足够优秀时就抛弃二分」。

若真要二分，模板是 §4 的固定 100 次迭代版本，check(r) 统计 \(d_i \le r^2\) 的权值和。

本题的题解文件尚未建立，上面的代码未经本地样例自动校验（实数 + special judge）。

BISHI91　拼接木棍（中等）

\(n \le 60\) 根小木棍（长度 \(\le 50\)）由若干等长大木棍砍成，求大木棍的最小可能长度。 题面见 原题。

这题被归到二分章，但它其实不满足二分的前提——这一点必须讲清楚。

设总长为 \(T\)，候选长度 \(L\) 必须满足 \(L \mid T\) 且 \(L \ge \max a_i\)。 「\(L\) 可行」关于 \(L\) 不单调：\(L=6\) 可行不代表 \(L=7\) 可行（\(7 \nmid T\) 时直接非法）， \(L\) 大也不一定更容易拼（约束是「恰好拼满」而非「不超过」）。 所以只能从小到大枚举 \(L\)，配搜索 + 剪枝验证，这是经典的 NOIP 1999《木棒》。

import sys


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    a = sorted((int(v) for v in data[1:1 + n]), reverse=True)   # 长的优先，剪枝更强
    total = sum(a)                                     # 总长固定，等于「根数 × 大木棍长度」
    used = [False] * n                                 # used[i]：第 i 根小木棍是否已被占用

    def dfs(L, target, done, cur, start):
        """L: 大木棍长度; target: 需要拼几根; done: 已拼好几根; cur: 当前这根已拼长度"""
        if done == target:
            return True                                # 全部拼完，成功
        if cur == L:
            return dfs(L, target, done + 1, 0, 0)      # 拼满一根，从头开始下一根
        prev = -1                                      # 本层上一次尝试过的长度，用于剪枝③
        for i in range(start, n):
            # 跳过：已用过 / 放进去会超长 / 与刚试过的那根等长（等长木棍完全等价）
            if used[i] or cur + a[i] > L or a[i] == prev:
                continue
            used[i] = True
            # start 传 i+1：同一根大木棍内部只按下标递增取，避免把同一组合枚举多次
            if dfs(L, target, done, cur + a[i], i + 1):
                return True
            used[i] = False                            # 回溯，恢复现场
            prev = a[i]                                # 剪枝③：同长度只试一次
            if cur == 0 or cur + a[i] == L:            # 剪枝④
                break
        return False

    # 「可行」对 L 不单调，只能从小到大枚举：L 必须整除总长，且不小于最长的那根小木棍
    for L in range(a[0], total + 1):
        if total % L == 0 and dfs(L, total // L, 0, 0, 0):
            print(L)                                   # 从小到大枚举，第一个成功的就是最小值
            return


main()

四个剪枝（少任何一个都会 TLE）：

剪枝	写法	理由
① 长度整除	total % L == 0	拼不满就不可能
② 降序排序 + start 递增	sorted(..., reverse=True)、range(start, n)	大的先放，失败得早；同一根内不重复枚举组合
③ 同长度只试一次	a[i] == prev: continue	长度相同的木棍等价
④ 首根 / 恰好填满失败即整体失败	if cur == 0 or cur + a[i] == L: break	当前根的第一根木棍放不进任何方案 ⟹ 该 \(L\) 无解；恰好填满还失败 ⟹ 后续更不可能

剪枝④是本题的灵魂：cur == 0 时，说明正在为一根新的大木棍挑第一段。 若挑最长的那段都失败了，那它必须出现在某根大木棍里、且哪里都放不下， 整个 \(L\) 直接判死。这一条把搜索树砍掉了绝大部分。

搜索与剪枝的系统讲法见 记忆化搜索与剪枝。

---

面试题单里的四道二分题

二分查找-I 是模板题：升序数组里找目标值的第一次出现下标。 按 §1 那张表，直接 i = bisect_left(a, x)，再判 i < len(a) and a[i] == x。 手写的话对应 §2 的「找第一个满足条件的位置」那种边界写法。

旋转数组的最小数字把有序性打了个折：数组是升序数组旋转之后的结果， 整体不再有序，但任取一段总有一半是有序的——二分仍然成立。 判据是拿 a[mid] 与 a[r] 比：小于则最小值在左半（含 mid）， 大于则在右半，相等时无法判断，只能 r -= 1 退一步。 最后这一条让最坏复杂度退化成 \(O(n)\)（全是相同元素时），这是允许重复元素的必然代价。 拿 a[mid] 与 a[l] 比是常见错法：数组没被旋转时会走错分支。

寻找峰值是 §6「二分的隐身形态」的好例子——数组根本无序， 但题目保证相邻元素不等且两端视为负无穷，于是 「a[mid] < a[mid+1] 就往右、否则往左」这条规则每次都能保住一个峰值在区间内。 二分要的从来不是有序，是「能一次排除一半」的单调判据。

二维数组中的查找给的是每行升序、每列也升序的矩阵。 逐行 bisect 是 \(O(n\log m)\)，能过； 但从右上角出发的走法更漂亮：比目标大就左移一列，比目标小就下移一行， 每步排除一整行或一整列，\(O(n+m)\)。 右上角是唯一同时具备「向左变小、向下变大」两个方向的起点，左下角同理， 另外两个角都不行——起点选错，这个做法就不成立。

另一处题库里的七道二分题

先把三道模板题归位。 LC 35. 搜索插入位置就是「第一个 \(\ge\) 目标的位置」，即 bisect_left 的返回值； LC 34. 在排序数组中查找元素的第一个和最后一个位置是它的左右两问， bisect_left 与 bisect_right 各调一次，后者减一即右端点，两问都不命中时返回 \([-1, -1]\)。 这两题直接调标准库比手写循环短且不会写错边界。 LC 74. 搜索二维矩阵的每行首元素大于上一行末元素，整个矩阵按行展平就是一个有序序列， 把下标 \(t\) 映射成 \((t / n, t \bmod n)\) 之后就是一次普通二分，\(O(\log(mn))\)。

LC 240. 搜索二维矩阵 II：条件放宽一点，二分就不成立了。 这里只保证每行递增、每列递增，行与行之间没有衔接，展平后并不有序。 可行的做法是从右上角出发：当前值大于目标就左移一列，小于目标就下移一行， 每步至少排除一行或一列，\(O(m + n)\)。 逐行二分是 \(O(m \log n)\)，在 \(m\) 与 \(n\) 同阶时反而更慢。 同名的两道题差的就是这一句前提，判据一变，解法整个换掉。

LC 33. 搜索旋转排序数组与 LC 153. 寻找旋转排序数组中的最小值：二分不需要整体有序。 二分真正要求的是「能用一次比较把答案排除在半边之外」，而不是数组有序。 旋转数组被断点分成两段，各自有序：拿 a[mid] 与 a[hi] 比一下就知道断点在哪一半， 另一半必然整段有序，于是目标在不在那一段可以直接判断。 LC153 只找最小值更简单：a[mid] > a[hi] 说明断点在右半，否则在左半含 mid，\(O(\log n)\)。 有重复元素时 a[mid] == a[hi] 无从判断，只能把 hi 减一退化到 \(O(n)\)。

LC 4. 寻找两个正序数组的中位数：二分的对象不是数组下标，而是「切一刀的位置」。 在较短的那个数组上二分「左半部分取多少个」，另一个数组取多少就随之定死； 一刀切合法的判据是「两侧交叉比较都不越界」，即左半的最大值不超过右半的最小值。 复杂度 \(O(\log \min(m, n))\)。 四条边界（某一侧取空、某一侧取满）要用正负无穷兜住，这是这题最容易写错的地方。 本章「二分的隐身形态」那一节说的就是这类题：被二分的量往往不是输入本身。

8　本章速查

需求	做法
有序数组查找	bisect，别手写
值在 \([l, r]\) 的个数	bisect_right(a, r) - bisect_left(a, l)
3.9 里按字段二分	先抽出关键字数组，bisect 无 key 参数
降序数组	存相反数转升序
最小的可行解	while lo < hi: mid=(lo+hi)//2; check→hi=mid else lo=mid+1
最大的可行解	while lo < hi: mid=(lo+hi+1)//2; check→lo=mid else hi=mid-1
死循环	lo = mid 却用了下取整 mid
mid 计算	Python 不会溢出，但必须用 //
实数二分	固定 100 次迭代，不要 while hi-lo>eps
实数能转整数	二分 \(r^2\) 而不是 \(r\)
单峰求极值	三分，每次缩到 \(2/3\)；整数域末尾留几个点暴力
「最大值最小」	二分答案的信号词
check 的实现	贪心 / 前缀和 / DP / 数据结构
不满足单调性	不能二分，改枚举 + 剪枝搜索（BISHI91）
bytes 逐字节比较	得到的是 int，ch == 'W' 恒假

模板	位置
四种整数二分边界	§2
二分答案骨架	§3
实数二分（固定迭代）	§4
三分（实数 / 整数）	§5