第 K 小（在值域上二分）

1. 核心原理

"第 K 小（或第 K 大）"是一类古老的查询：给一个集合 S，求 S 升序排列后位置 k 上的元素。当 S 是单个有序数组时直接索引即可；当 S 来源于矩阵、双数组乘积、子数组和等"组合结构"时，朴素枚举所有元素再排序的代价不可接受。

本章把上一章的二分思路再推一步——二分对象从答案值搬到统计量。对候选值 x 数一下"S 里 ≤ x 的元素有多少个"，得到计数函数 count_leq(x)。这个函数关于 x 单调，于是可以二分 x 找第 K 小。

朴素枚举为什么不够

最直接的写法有两种：

• 铺平排序：把 S 中所有元素列出来排序取第 k 个。代价 O(|S| log |S|)，|S| 大到 10⁹ 量级时直接爆。
• 最小堆 K 路归并：每次弹出当前最小、推入它的"后继"。代价 O(k log m)，k 大时（典型如乘法表的 k ≤ m × n = 10⁹）也撑不住。

两种暴力的共性是复杂度和集合大小 |S| 或 k 死锁。如果能把复杂度跟 k 脱钩、只依赖值域大小 V，就能处理 k 极大的场景。

算法的关键洞察

考虑计数函数 count_leq(x) = S 里 ≤ x 的元素个数。它有两个性质：

• 单调性：x 增大时 count_leq(x) 只增不减——多了一个候选值就多了能"包住"的元素，不可能少。这是二分能立住的根。
• 与答案的关系：设第 k 小是 ans。那么 count_leq(ans) >= k（前 k 个 ≤ ans 的全在），且 count_leq(ans - 1) < k（少一个就不够 k 个）。换句话说，ans 就是"第一个让 count_leq >= k 的值"——正是 lower_bound 的形状。

把这件事抽象成一句话：

二分对象从下标或答案值换成统计量，判定函数从 nums[mid] >= target 或 check(mid) 换成 count_leq(mid) >= k。骨架完全不变，所有活儿集中在如何 O(n) 实现 count_leq。

复杂度从 O(|S|) 或 O(k log m) 降到 O(n log V)，跟 k 完全脱钩。V 是值域大小，log V 通常 ≤ 60（即使 V = 10¹⁸）。

另一个值得注意的性质——二分得到的整数答案一定是 S 中的真实元素。证明：循环结束 lo = L，由不变量 count_leq(L) >= k 且 count_leq(L - 1) < k，两式相减 count_leq(L) - count_leq(L - 1) > 0，差值正是"值等于 L 的元素个数"——必然 ≥ 1。这保证答案自动落在合法集合里，不需要"找最近真实值"的后处理。

套路类型一览

count_leq(x) 的实现是这一族题的核心技术，常见五种形态：

三章串起来就是：

三种模式骨架完全相同，区别只在"怎么定义判定函数"。识别第三类题的关键信号：题目问"第 k 小 / 第 k 大"，而你能 O(n) 算 count_leq(x) 或 count_geq(x)。

2. 通用模板

骨架仍是 lower_bound 一字不差——搜索区间 [lo, hi) + while lo < hi + 看判定函数。区别只在判定函数换成 count_leq(mid) >= k，以及二分对象是值域 [min(S), max(S) + 1)。

def kth_smallest_by_value(lo: int, hi: int, k: int, count_leq) -> int:
    """
    在值域 [lo, hi) 上找第 k 小。
    count_leq(x) 返回 ≤ x 的元素个数（必须关于 x 单调非降）。
    返回值保证是集合中实际存在的元素。
    """
    while lo < hi:
        mid = (lo + hi) // 2
        if count_leq(mid) >= k:
            hi = mid           # mid 可能就是答案，往左收
        else:
            lo = mid + 1       # 还没达到 k 个，往右
    return lo


# 浮点版本（如 LC 786）：闭区间 + 固定迭代
def kth_smallest_float(lo: float, hi: float, k: int, count_leq) -> float:
    """浮点二分固定 100 次迭代，避免 while hi - lo > eps 的精度陷阱。"""
    for _ in range(100):
        mid = (lo + hi) / 2
        if count_leq(mid) >= k:
            hi = mid
        else:
            lo = mid
    return lo

// 整数版：[lo, hi) 左闭右开
int kthSmallestByValue(int lo, int hi, int k, IntPredicate countAtLeastK) {
    // countAtLeastK.test(x) ≡ (count_leq(x) >= k)
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (countAtLeastK.test(mid)) hi = mid;        // 候选答案，往左收
        else lo = mid + 1;                            // 还不够 k 个
    }
    return lo;
}

// 浮点版：[lo, hi] 闭区间 + 固定 100 次迭代
double kthSmallestFloat(double lo, double hi, int k, DoublePredicate countAtLeastK) {
    for (int i = 0; i < 100; i++) {
        double mid = (lo + hi) / 2;
        if (countAtLeastK.test(mid)) hi = mid;
        else lo = mid;
    }
    return lo;
}

// 整数版：[lo, hi) 左闭右开
long long kthSmallestByValue(long long lo, long long hi, int k,
                             function<long long(long long)> countLeq) {
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (countLeq(mid) >= k) hi = mid;             // 候选答案，往左收
        else lo = mid + 1;                            // 还不够 k 个
    }
    return lo;
}

// 浮点版：[lo, hi] 闭区间 + 固定 100 次迭代
double kthSmallestFloat(double lo, double hi, int k,
                        function<long long(double)> countLeq) {
    for (int i = 0; i < 100; i++) {
        double mid = (lo + hi) / 2;
        if (countLeq(mid) >= k) hi = mid;
        else lo = mid;
    }
    return lo;
}

模板的关键点：

• 值域上下界：lo 取 S 的最小可能值，hi 取 S 的最大可能值 + 1（整数左闭右开）。LC 378 取 [matrix[0][0], matrix[n-1][n-1] + 1)。下界给小一点不影响正确性（多走一两步），但上界必须 ≥ 真实答案。
• 判定函数：count_leq(mid) >= k——找的是"第一个让累计 ≥ k 个的 x"。如果题目要的是第 k 大，可改用 count_geq(mid) >= k 同时把 lo 与 hi 镜像，或者转化为"第 (|S| - k + 1) 小"。
• count 函数必须严格单调非降：增加候选 x 只让计数增不让计数减。整数值域上这几乎自动成立；浮点场景要警惕数值误差导致的非单调。
• 整数二分的"答案自动对齐"：由前面证明，整数版本结束时 lo 一定是 S 中的真实元素。浮点版本则需要在 count 过程中顺手维护"当前最大 ≤ x 的元素"（如 LC 786 的 best_p / best_q），二分结束后返回这个维护值。
• 负数取整：跨语言时，Java / C++ 的 / 对负数是向零截断（-7 / 2 = -3 而非 -4），Python 的 // 是 floor 除法。涉及负数的 count 函数（如 LC 2040）需要手动修正。

3. 母题精讲

前两章立了两根柱子：第一章在下标上二分，第二章在答案值上二分。这一章再推一步——把二分搬到第三个对象：统计量。下面从 LC 378 出发立模板。

LeetCode 378. 有序矩阵的第 K 小

链接：LeetCode 378

题意：给一个 n × n 的矩阵，每行从左到右升序、每列从上到下升序。返回矩阵里第 k 小的元素（不是去重的第 k 个，而是按升序排出来的第 k 个）。

数据范围：

• n：1 到 300
• matrix[i][j]：−10⁹ 到 10⁹
• k：1 到 n²

示例：

输入：matrix = [[ 1,  5,  9],
              [10, 11, 13],
              [12, 13, 15]], k = 8
输出：13

暴力一：直接排序

最直接的写法——把整个矩阵铺平排序，取第 k 个：

class Solution:
    def kthSmallest_sort(self, matrix: list[list[int]], k: int) -> int:
        flat = [x for row in matrix for x in row]
        flat.sort()
        return flat[k - 1]

时间 O(n² log n²) = O(n² log n)，空间 O(n²)。功能完全正确，但完全没有用到"行 / 列升序"的结构——题目给的结构被白白扔了。

暴力二：最小堆

进一步——每次弹出当前最小，把它的"右邻 + 下邻"塞进堆。弹 k 次后弹出的就是答案：

import heapq

class Solution:
    def kthSmallest_heap(self, matrix: list[list[int]], k: int) -> int:
        n = len(matrix)
        heap = [(matrix[0][0], 0, 0)]    # (val, i, j)
        seen = {(0, 0)}
        for _ in range(k - 1):
            val, i, j = heapq.heappop(heap)
            for di, dj in [(1, 0), (0, 1)]:
                ni, nj = i + di, j + dj
                if 0 <= ni < n and 0 <= nj < n and (ni, nj) not in seen:
                    seen.add((ni, nj))
                    heapq.heappush(heap, (matrix[ni][nj], ni, nj))
        return heap[0][0]

时间 O(k log n)（堆里最多 O(n) 个元素），空间 O(n)。已经用上了部分结构，比排序好。LC 数据范围下（n ≤ 300, k ≤ 9 × 10⁴）这个解能 AC。

但有两点不爽：

一是复杂度跟 k 死锁。题目要是把 k 设到 n² = 9 × 10⁴，堆解 O(k log n) ≈ 10⁵ × 8 ≈ 10⁶，OK；但同类问题里 k 量级动辄 10¹² 时（LC 668 的乘法表），堆解直接爆。

二是值域这个天然有界结构一点没用上。matrix[0][0] 到 matrix[n-1][n-1] 就是值域，差值通常 ≤ 2 × 10⁹，log V ≈ 31。如果能把复杂度跟 k 解耦、变成 O(n log V)，那 k 多大都不怕。

下面这个观察让这件事成立。

count_leq(x) 关于 x 单调递增

看这个函数：count_leq(x) = 矩阵里 ≤ x 的元素个数。它有两个性质：

一是 单调性。x 增大时 count_leq(x) 只增不减——多了一个候选值就多了能"包住"的元素，不可能少。这就是二分能立住的根。

二是 与答案的关系。设第 k 小是 ans。那 count_leq(ans) >= k（前 k 个 ≤ ans 的全在），而 count_leq(ans - 1) < k（少一个就不够 k 个）。换句话说，ans 就是"第一个让 count_leq >= k 的值"——正是 lower_bound 的形状。

于是就可以在值域 [matrix[0][0], matrix[n-1][n-1]] 上二分 x，每轮 O(n) 数一下 count_leq(mid)，根据是否 ≥ k 调整区间。复杂度 O(n · log V)，跟 k 完全脱钩。

剩下的活儿就一件：怎么 O(n) 算 count_leq(x)？这是"在值域上二分"这一族题的核心技术。下面把这件事讲到底。

4. 五道例题：count 函数怎么造

4.1 LC 378 回到开头这道题

链接：LeetCode 378

题意：给一个 n × n 的矩阵，每行从左到右升序、每列从上到下升序。返回矩阵里第 k 小的元素。

数据范围：n 1 到 300，matrix[i][j] ±10⁹，k 1 到 n²。

count_leq(x) 怎么 O(n) 算？关键在利用行列同时单调，沿"左下到右上"的对角线扫——从左下角 (n-1, 0) 出发：

• matrix[i][j] <= x：这一列从 0 到 i 整段都 ≤ x（列升序），一次加 i + 1，然后向右走 j += 1。
• matrix[i][j] > x：这一行从 j 往右都更大，没贡献，向上走 i -= 1。

走 O(n) 步就扫完。下面这个交互演示走一遍 count_leq(11) 在示例矩阵上的过程：

最后 count_leq(11) = 5，意味着矩阵里有 5 个元素 ≤ 11，所以第 6 小是大于 11 的某个数。题目问 k=8 时，需要继续二分到更大的 x 上去。

代码：

class Solution:
    def kthSmallest(self, matrix: list[list[int]], k: int) -> int:
        n = len(matrix)

        def count_leq(x: int) -> int:
            cnt, i, j = 0, n - 1, 0
            while i >= 0 and j < n:
                if matrix[i][j] <= x:
                    cnt += i + 1            # 这一列从 0 到 i 都满足
                    j += 1
                else:
                    i -= 1
            return cnt

        lo, hi = matrix[0][0], matrix[n - 1][n - 1] + 1
        while lo < hi:
            mid = (lo + hi) // 2
            if count_leq(mid) >= k:
                hi = mid
            else:
                lo = mid + 1
        return lo

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        int lo = matrix[0][0], hi = matrix[n - 1][n - 1] + 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (countLeq(matrix, mid) >= k) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }

    private int countLeq(int[][] matrix, int x) {
        int n = matrix.length, cnt = 0, i = n - 1, j = 0;
        while (i >= 0 && j < n) {
            if (matrix[i][j] <= x) { cnt += i + 1; j++; }
            else { i--; }
        }
        return cnt;
    }
}

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int n = matrix.size();
        int lo = matrix[0][0], hi = matrix[n - 1][n - 1] + 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (countLeq(matrix, mid) >= k) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }

private:
    int countLeq(vector<vector<int>>& matrix, int x) {
        int n = matrix.size(), cnt = 0, i = n - 1, j = 0;
        while (i >= 0 && j < n) {
            if (matrix[i][j] <= x) { cnt += i + 1; j++; }
            else { i--; }
        }
        return cnt;
    }
};

复杂度 O(n log V) ≈ 300 × 31 ≈ 10⁴，毫秒级。框架同前两章，唯一的活儿是把 count_leq 写漂亮。

Follow-up：如果矩阵不是直接给的、而是 i × j 这样的乘法表呢？count 怎么算？

4.2 LC 668 乘法表中第 K 小

链接：LeetCode 668

题意：一个 m × n 的乘法表，第 i 行第 j 列的值是 i × j（行列都从 1 开始编号）。返回这个表里第 k 小的数。

数据范围：

• m、n：1 到 3 × 10⁴
• k：1 到 m × n

示例：

输入：m = 3, n = 3, k = 5
输出：3
解释：乘法表
1 2 3
2 4 6
3 6 9
按升序排列是 [1, 2, 2, 3, 3, 4, 6, 6, 9]，第 5 小是 3。

这道题用 LC 378 的"右上到左下扫"也能做（O((m+n) log V)），但更简洁的写法是利用"行 i 内 ≤ x 的元素个数 = min(n, x // i)"——每行 O(1) 求和：

class Solution:
    def findKthNumber(self, m: int, n: int, k: int) -> int:
        def count_leq(x: int) -> int:
            return sum(min(n, x // i) for i in range(1, m + 1))

        lo, hi = 1, m * n + 1
        while lo < hi:
            mid = (lo + hi) // 2
            if count_leq(mid) >= k:
                hi = mid
            else:
                lo = mid + 1
        return lo

复杂度 O(m log(mn)) ≈ 3 × 10⁴ × 30 ≈ 10⁶，毫秒级。count_leq 的实现关键：第 i 行的元素是 i, 2i, 3i, ..., n·i，其中 ≤ x 的有 min(n, ⌊x/i⌋) 个。这就是为什么"每行 O(1)"——乘法表的结构帮了大忙。

Follow-up：上面两题数的都是"矩阵里 ≤ x 的元素"。如果题目从"元素"变成"配对距离"呢？给你一个数组，第 k 小的"两个元素之差"是多少？

4.3 LC 719 第 K 小的距离对

链接：LeetCode 719

题意：给一个整数数组 nums。任意两个不同下标 (i, j) 组成一个"对"，其距离定义为 |nums[i] − nums[j]|。返回所有 C(n, 2) 对里第 k 小的距离。

数据范围：

• nums.length：2 到 10⁴
• nums[i]：0 到 10⁶
• k：1 到 nums.length × (nums.length − 1) / 2

值域怎么定？先把 nums 排序，最小距离是 0（如果有重复），最大距离是 max(nums) - min(nums)。在 [0, max - min] 上二分候选距离 d。

count_leq(d) 怎么 O(n) 算？这就是套路点——排序后用滑动窗口：右端固定为 j，找最小的 i 使 nums[j] - nums[i] <= d，那么 (i, j), (i+1, j), ..., (j-1, j) 都是合法对，共 j - i 个。j 向右移动时 i 单调向右——经典双指针。

class Solution:
    def smallestDistancePair(self, nums: list[int], k: int) -> int:
        nums.sort()
        n = len(nums)

        def count_leq(d: int) -> int:
            cnt, i = 0, 0
            for j in range(n):
                while nums[j] - nums[i] > d:
                    i += 1
                cnt += j - i                # (i, j), (i+1, j), ..., (j-1, j)
            return cnt

        lo, hi = 0, nums[-1] - nums[0] + 1
        while lo < hi:
            mid = (lo + hi) // 2
            if count_leq(mid) >= k:
                hi = mid
            else:
                lo = mid + 1
        return lo

复杂度 O(n log n) 排序 + O(n log V) 二分 + count_leq，整体 O(n log V) ≈ 10⁴ × 30 ≈ 3 × 10⁵。

双指针为啥成立？因为数组排序后 j 右移时 nums[j] 不减，所以满足 nums[j] - nums[i] <= d 的最左 i 也不减——i 永远不需要回头，双指针总步数 O(n)。这就是"排序后单调"这条性质的核心用法。

Follow-up：再升级一下——如果"对"不是两数差，而是两数构成的分数 nums[i] / nums[j] 呢？

4.4 LC 786 第 K 个最小素数分数

链接：LeetCode 786

题意：给一个严格升序的素数数组 arr（含 1），对所有 i < j 构造分数 arr[i] / arr[j]。返回第 k 小的分数，以 [arr[i], arr[j]] 的形式输出。

数据范围：arr.length 2 到 1000，arr[i] 2 到 3 × 10⁴。

值域：分数最小是 arr[0] / arr[-1]（趋近 0），最大是 arr[-2] / arr[-1]（趋近 1）。在 [0, 1] 上做浮点二分，候选 x 是个浮点小数。

count_leq(x) 怎么 O(n) 算？固定分子 i，找最大的 j 使 arr[i] / arr[j] <= x，等价 arr[j] >= arr[i] / x。arr 升序，i 增大时这个 j 也单调——又是双指针。同时顺手记一下"满足条件下最大的分数"，方便最后输出 [arr[i], arr[j]]。

class Solution:
    def kthSmallestPrimeFraction(self, arr: list[int], k: int) -> list[int]:
        n = len(arr)

        def count_leq(x: float) -> tuple[int, int, int]:
            """返回 (count, best_p, best_q)，best 是 ≤ x 范围里最大的分数对应的 p, q"""
            cnt, j = 0, 1
            best_p, best_q = 0, 1           # 维护 ≤ x 的最大分数 p/q
            for i in range(n - 1):
                while j < n and arr[i] / arr[j] > x:
                    j += 1
                if j < n:
                    cnt += n - j
                    # arr[i] / arr[j] 是当前 i 的最大且 ≤ x 的分数
                    if arr[i] * best_q > best_p * arr[j]:
                        best_p, best_q = arr[i], arr[j]
            return cnt, best_p, best_q

        lo, hi = 0.0, 1.0
        # 浮点二分：固定 100 次迭代兜底
        for _ in range(100):
            mid = (lo + hi) / 2
            cnt, p, q = count_leq(mid)
            if cnt == k:
                return [p, q]
            elif cnt > k:
                hi = mid
            else:
                lo = mid
        # 兜底：返回最后一次记录的 p, q
        _, p, q = count_leq(lo)
        return [p, q]

复杂度 O(100n) ≈ 10⁵，毫秒级完成。

这里有两个不平凡的实现细节：

一是浮点二分的精度处理——固定迭代次数而不是 while hi - lo > eps。上一章 二分答案 已经详细讨论过，这里直接套就行。

二是 count_leq 在数 cnt 的同时维护当前能找到的"最大但 ≤ x"的分数 (best_p, best_q)——因为浮点二分收敛到的 x 不一定恰好对应某个分数值，需要在 count 过程中顺手记下真正的分数对。这是"答案对齐"的小技巧。

Follow-up：上面四题的 count 都在"一组确定的数"里数。如果"一组数"本身是动态生成的——两个数组的所有乘积，而且要考虑正负号呢？

4.5 LC 2040 两个有序数组的第 K 小乘积

链接：LeetCode 2040

题意：给两个升序数组 nums1、nums2，所有 nums1[i] * nums2[j] 构成 m × n 个乘积。返回这些乘积中第 k 小的（按数值升序排）。

数据范围：

• nums1.length、nums2.length：1 到 5 × 10⁴
• nums1[i]、nums2[j]：−10⁵ 到 10⁵
• k：1 到 m × n，最大可达 2.5 × 10⁹

k 能到 2.5 × 10⁹，堆解法直接爆，必须走值域二分。值域：乘积 nums1[i] * nums2[j] 范围是 ±10¹⁰，二分 lo = -10¹⁰、hi = 10¹⁰ + 1。

count_leq(x) 的难点全在正负号——对每个 nums1[i]，要数 nums2[j] 中有多少个使 nums1[i] * nums2[j] <= x：

• nums1[i] > 0：等价 nums2[j] <= x / nums1[i]，二分 nums2 找上界
• nums1[i] < 0：等价 nums2[j] >= x / nums1[i]（不等号翻转），二分 nums2 找下界
• nums1[i] == 0：所有 nums2[j] 都给乘积 0，比较 0 <= x 即可

每个 i 做一次 nums2 上的二分，整体 O((m + n) log V) 或 O(m log n · log V)：

from bisect import bisect_right, bisect_left

class Solution:
    def kthSmallestProduct(self, nums1: list[int], nums2: list[int], k: int) -> int:
        m, n = len(nums1), len(nums2)

        def count_leq(x: int) -> int:
            cnt = 0
            for a in nums1:
                if a > 0:
                    # nums2[j] <= x / a，但要小心整数除法对负数的处理
                    # ⌊x / a⌋ 当 x >= 0 时等于 x // a；x < 0 时需要 Python 的 floor 除法
                    cnt += bisect_right(nums2, x // a if x >= 0 else -((-x + a - 1) // a))
                elif a < 0:
                    # nums2[j] >= ⌈x / a⌉，等价 x - a*nums2[j] >= 0
                    # 二分找第一个 nums2[j] >= ⌈x / a⌉
                    # 由于 a < 0，⌈x/a⌉ = -((-x) // (-a)) ... 浮点辅助也行
                    threshold = -(-x // -a) if x % a == 0 else -((-x) // (-a))
                    # 简洁稳定的做法：用 Python 的 -(-x // a)（向上取整）
                    threshold = -(-x // a)
                    cnt += n - bisect_left(nums2, threshold)
                else:  # a == 0
                    if 0 <= x:
                        cnt += n
            return cnt

        lo, hi = -(10**10), 10**10 + 1
        while lo < hi:
            mid = (lo + hi) // 2
            if count_leq(mid) >= k:
                hi = mid
            else:
                lo = mid + 1
        return lo

复杂度 O((m + n) · log V · log(m + n)) 或更优。这道题工程上最难处理的不是二分外层，而是 count_leq 里负数的向上 / 向下取整——Python 的 // 对负数也是向下取整，可以用 -(-x // a) 表示向上取整，但 Java / C++ 的 / 对负数是向零截断，要手写 floor 函数。

注意：这段 count_leq 代码处理负数的部分相当绕，重点不是背完整代码，而是讲清楚"按 nums1[i] 正负分三类、二分 nums2"的思路 + 给出每类的 count 公式。框架还是那个框架，套路还是那个套路，只是 count 函数加了一层"分类讨论"的外壳。

5. 边界、易错与复杂度

把五道题里散见的踩坑点和复杂度统一汇总。

count 函数必须严格单调非降

跟上一章"判定函数必须单调"是一回事——count_leq(x) 关于 x 不能横跳。整数值域上这个性质几乎自动成立（增加候选 x 只会让"≤ x"包含更多元素），浮点场景下要小心数值误差导致的非单调。一句话：单调性是二分的命，三章都一样。

值域取闭区间还是开区间

整数二分按 [lo, hi) 模板，hi 取 max_value + 1；浮点二分用 [lo, hi] 闭区间（因为浮点没有"+1"）。LC 786 浮点版的 hi = 1.0 是闭区间。

浮点二分要兜底

LC 786 这种浮点版本必须用固定迭代次数（100 次）而不是 while hi - lo > eps——后者在边角输入会因累积误差永不收敛。100 次迭代覆盖 2¹⁰⁰ 倍精度收缩，远超 IEEE 754 双精度尾数位的需求。

为什么二分出来的整数 lo 一定是矩阵元素

证明在 §1 已经给过：count_leq(lo) - count_leq(lo - 1) > 0 意味着值等于 lo 的元素至少有一个。这个性质对所有整数版本都适用（LC 378 / 668 / 719 / 2040），让我们不用做后处理对齐。

浮点版本（LC 786）不存在这个问题——题目要求返回分数对 [p, q]，所以 count_leq 在数 cnt 时顺手记下当前最大的 p / q ≤ mid，二分结束后直接返回这对值。

负数与取整

LC 2040 是这一族里唯一涉及负数的题，主要难度在 count 函数处理负数除法的向上/向下取整。

工程上常用的"对负数稳定"floor / ceil 实现：

def floor_div(x, a):
    return x // a              # Python 原生就是 floor
def ceil_div(x, a):
    return -(-x // a)          # Python 技巧

Java / C++ / Go 里 x / a 对负数是向零截断（比如 -7 / 2 = -3 而不是 -4），如果 x 和 a 异号且 x % a != 0 需要手动修正 result - 1。

复杂度速查

7. 小结

到这里二分系列三章串通了：

第一章 二分查找 在数组下标上找单调边界，模板就是 lower_bound。

第二章 二分答案 把模板搬到答案值域上，关键是识别"check(x) 关于 x 单调"。

第三章（本章）再推一步——二分对象从答案值换成统计量，给候选 x 数 count_leq(x)，再用同一份 lower_bound 模板。

三种模式骨架一字不差——搜索区间 [lo, hi) + while lo < hi + 看判定函数。区别只在"判定函数的语义"。掌握了这层抽象之后，看到新题先问三件事：

1. 有没有一个"候选值 x"可以二分？
2. 这个 x 对应的"check / count"函数关于 x 是不是单调？
3. check / count 怎么 O(n) 实现？

三个问题都有答案，直接套模板就完了。

下一章进入 滑动窗口 系列——一个看起来跟二分完全不同的套路，但本质上也是在啃"单调性"这块骨头，只不过是在"扫一遍数组"这件事上做到了极致。

对应灵神题单：值域二分 / 第 K 小 / 第 K 大

进一步阅读：灵茶山艾府《二分算法题单》第三部分；LeetCode 第 K 小标签 下的高频题