题目重点：已知整数取值范围时二分秩；题目未明确值域，任意实数精确中位数不可由有限次计数查询保证。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练代码额外假设原值为已知闭区间 [L,R] 内整数，Oracle `count_greater(x)` 精确返回严格大于 x 的元素数。
- 偶数 N 同时返回下中位数、上中位数和二者平均数；真实接口若只要某一种，需先确认。
- Oracle 查询成本单独记 Q，不假设内部是 O(1)；若输入是任意实数且只给严格比较计数，有限查询通常无法精确恢复未知值。
解题路线
- 由 `count_at_most(x)=N−count_greater(x)` 得到前缀秩；对第 k 小值，找最小整数 x 使 count_at_most(x)≥k。
- 因为 count_at_most 随 x 非降，二分 [L,R]；对 k=(N+1)//2 和 k=(N+2)//2 各查一次，覆盖奇偶长度与重复值。
- 若 Oracle 同时返回 less/greater，可算等于 x 的数 `N−less−greater`，用于验证边界与重复元素。
- 信息边界：对任意实数，即使做有限次阈值查询，两个不同实数可落在所有查询阈值同一侧而给完全相同回答，因此不能保证精确值；须有整数/离散候选集、精度目标或原值可访问。
- 训练代码在 1,715 个短整数多重集上，以排序后的两个中位位置独立对照。
手动走一遍
数组隐藏为 [1,2,2,9]，N=4。查 x=2 时 greater=1，故 ≤2 的有 3 个；第 2 小和第 3 小都可二分定位为 2，平均中位数也是 2。若隐藏值是 1.234567... 的未知实数，有限次只问大小计数不能确定全部小数位。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from collections.abc import Callable
def median_from_count_greater(
count: int,
lower_bound: int,
upper_bound: int,
count_greater: Callable[[int], int],
) -> tuple[int, int, float]:
"""Integer domain [L,R]; oracle returns number of values strictly > x."""
if count <= 0 or lower_bound > upper_bound:
raise ValueError("non-empty data and valid integer bounds required")
def kth(rank: int) -> int:
low, high = lower_bound, upper_bound
while low < high:
middle = (low + high) // 2
count_at_most = count - count_greater(middle)
if count_at_most >= rank:
high = middle
else:
low = middle + 1
return low
left = kth((count + 1) // 2)
right = kth((count + 2) // 2)
return left, right, (left + right) / 2
复杂度
每个 order statistic 需 O(log(R−L+1)) 次 Oracle 查询，额外 O(1) 空间；总运行时间乘以 Oracle 单次成本。若值域离散但很大、只给候选值列表，可在排序后的候选集合上二分。
易错点与追问
容易失分的边界
- 把 `greater(x)` 直接当 `≤x` 而没用 N 补集。
- 有重复值时只凭等于 N/2 的比较计数找位置，跳过一整段相同值。
- 奇偶中位数口径未签便给唯一数值。
- 题目未明确值域，却宣称二分任意实数能精确返回中位值。
- 把 Oracle 查询视为免费的 O(1) 而不问数据规模/实现。
继续深挖
- 若整数无已知边界，怎样先指数扩张找到包含中位数的区间？
- 若 Oracle 有误差 ±ε，能给中位数什么保证？
- 只需 ε 近似的实数中位数时如何选停止条件？
- 若支持批量阈值查询，怎样减少网络往返？
