如何用计数函数二分查找第 K 小元素？

简化版

当题目要求第 K 小，但元素集合太大、不能直接排序时，可以二分“答案值”。

核心不是判断某个下标，而是写一个 count(x)：统计小于等于 x 的元素有多少个。

如果 count(x) >= k，说明第 K 小不大于 x，右边界左移；否则说明 x 太小，左边界右移。

这种题的关键是：答案空间有序，计数函数随 x 单调不减。

详细版

第 K 小问题常见有两种做法：堆、排序、快速选择，或者二分答案。

二分答案适合“值域有边界，且能快速统计有多少元素不超过某个值”的场景。

例如乘法表第 K 小：m * n 的表不能真的展开排序，但对于一个值 x，第 i 行小于等于 x 的数量是 min(n, x / i)，所有行累加即可。

判断逻辑是：

function enough(x) {
  return countLessOrEqual(x) >= k
}

然后找第一个让 enough(x) 为真的值。

这类问题本质是 lower_bound：在值域 [minValue, maxValue] 中找最小可行答案。

容易错的地方是把 count(x) == k 当作终止条件。第 K 小的值可能重复，count(x) 经常会跳过 k，所以应该用 >= k 收缩右边界。

完整版教学

1. 题目真正问的不是“第 K 个下标”

第 K 小听起来像排序后的下标问题，但很多面试题故意不给你可排序的数组。

例如：

m x n 乘法表有 m * n 个数，规模可能达到 9 * 10^8
有序矩阵第 K 小，矩阵已经局部有序，但整体展开成本高
多个有序结构合并后的第 K 小，直接合并会浪费空间

这时要换一个角度：答案本身一定落在某个值域里。

如果能回答“有多少个数小于等于 x”，就能判断第 K 小是否已经被覆盖。

第 K 小的核心判断是：当小于等于 x 的元素数量至少为 K 时，答案一定不大于 x。

2. 单调性来自计数函数

设 count(x) 表示集合中小于等于 x 的元素个数。

当 x 增大时，能被统计进来的元素只会变多，不会变少。

x 的变化	count(x) 的变化	对答案的含义
x 偏小	count(x) < k	第 K 小比 x 大
x 足够大	count(x) >= k	第 K 小不大于 x
x 继续增大	count(x) 继续不减	仍然可行，但不一定最小

所以目标是找第一个满足 count(x) >= k 的值。

这就是在答案值域上做 lower_bound。

3. 标准模板

用闭区间写法通常最稳：

function kthSmallest(low, high, k) {
  while (low < high) {
    const mid = Math.floor((low + high) / 2)
    if (countLessOrEqual(mid) >= k) {
      high = mid
    } else {
      low = mid + 1
    }
  }
  return low
}

这里 low 和 high 都是值，不是数组下标。

循环结束时，low === high，它就是第一个计数达到 K 的值。

4. 以乘法表第 K 小为例

乘法表第 i 行是：

i, 2i, 3i, ..., n*i

小于等于 x 的个数为：

Math.min(n, Math.floor(x / i))

完整计数：

function countLessOrEqualInTable(m, n, x) {
  let count = 0
  for (let i = 1; i <= m; i++) {
    count += Math.min(n, Math.floor(x / i))
  }
  return count
}

如果 m = 3, n = 3，乘法表展开是 [1,2,2,3,3,4,6,6,9]。

第 5 小是 3。当 x = 3 时，count(3) = 5，刚好可行。

5. 为什么不能依赖 count(x) == k

重复值会让计数跳跃。

在上面的乘法表中：

count(1) = 1
count(2) = 3
count(3) = 5

如果找第 4 小，答案仍然是 3，但没有任何 x 让 count(x) == 4。

所以判断必须是 count(x) >= k。

6. 常见面试追问

误区：看到第 K 小就直接排序。 如果候选集合太大，排序可能超时或爆内存，要先观察是否能写计数函数。
误区：二分下标而不是二分值域。 这类题没有明确数组下标，二分的是可能答案。
误区：把等于 K 当作命中。 重复元素会让计数跳过 K，应该找第一个 count(x) >= k 的值。
追问：如果值域很大怎么办？ 二分复杂度是 O(logV)，只要计数函数足够快，值域大也能接受。
追问：如何证明返回值一定存在？ 因为 high 取最大可能值时，count(high) 至少等于总元素数，必然大于等于 K。

这些追问的共同点是考察你能不能把“排名问题”转化成“可行性边界问题”。

7. 复杂度分析

如果值域大小为 V，每次计数成本为 C，总复杂度是：

O(C * logV)

乘法表中 C = m，所以复杂度是 O(m log(mn))。

空间复杂度通常是 O(1)。

8. 面试表达模板

可以这样回答：

“第 K 小不一定要真的排序。我会二分答案值 x，然后设计一个计数函数统计小于等于 x 的元素数量。因为 x 越大，计数越大，具备单调性。如果计数大于等于 K，说明答案不超过 x，收缩右边界；否则说明 x 太小，收缩左边界。最后得到第一个满足计数不少于 K 的值。”

简化版

详细版