仅可判断猜测是否过低时Python大范围查找最小有效数的高效方法

最高效实现方式 #

该场景属于典型的左边界查找问题，校验函数的返回天然满足单调性要求：所有小于最小有效数的测试值返回False，所有大于等于最小有效数的测试值返回True，最高效的实现方案为二分查找（左边界变种），时间复杂度为对数级。
如果提前已知数值的上下界范围，可以直接执行二分查找；如果是无明确上限的极大数值范围，可以先通过指数倍增确定右边界，再执行二分查找，整体时间复杂度依然为O(log x)，x为最小有效数的实际大小，和已知边界的二分查找效率完全一致。

代码实现示例 #

def find_min_valid(check_func, start_low: int = 0) -> int:
    # 指数倍增确定右边界，适配无上限的大数值场景
    low = start_low
    high = 1
    while not check_func(high):
        low = high
        high *= 2
    # 左边界二分查找锁定最小有效值
    while low < high:
        mid = (low + high) // 2
        if check_func(mid):
            high = mid
        else:
            low = mid + 1
    return low

Python原生支持任意精度的大整数运算，倍增过程不会出现溢出问题，完美适配大数值范围的查找需求。

非线性解决方案说明 #

不存在比对数复杂度更优的非线性方案：每次调用校验函数只能获得1比特的信息，要从S个可能的数值中确定唯一的最小有效值，理论上至少需要log2(S)次查询，二分查找的复杂度已经达到了理论下界，没有进一步优化的空间。
如果你提到的「非线性」是指区别于从0开始逐次加1测试的线性遍历方案，那么上述的倍增+二分方案本身就属于非线性方案，它的查询次数不会随目标值大小线性增长，而是随目标值的位数增长。 #

内容的提问来源于stack exchange，提问作者Beta Tester