基于几何均值的二分搜索：何时收敛速度更快？

核心结论 #

当目标值更靠近初始下界，且初始搜索区间的跨度（h/l）极大时，几何均值搜索的收敛速度会显著快于算术均值搜索。具体来说：

• 若目标值小于初始区间的几何均值 √(l*h)，且 h/l 的比值超过10^10这类数量级，几何均值搜索几乎总能以更少迭代次数收敛。

原理分析 #

两种搜索的本质是对不同空间的二分划分：

• 算术均值搜索是线性空间的二分：每次迭代将当前区间的线性长度减半，收敛效率取决于区间的线性跨度 h-l。
• 几何均值搜索等价于对数空间的算术二分：对变量取自然对数后，ln(m) = (ln(l)+ln(h))/2，每次迭代将对数空间的区间长度减半，收敛效率取决于区间的对数跨度 ln(h)-ln(l)。

当目标值靠近下界 l 时，在对数空间中，目标与 l 的距离远小于与 h 的距离，几何均值的每次迭代能精准缩小靠近目标的区间；而算术均值在超宽线性区间下，前几次迭代的中点会极度靠近 h，需要多次迭代才能逼近靠近 l 的目标。

实验结果验证 #

你固定 l=1、h 从10^1到1050的测试结果完全契合上述逻辑：

• 当随机目标覆盖整个 [2,h] 区间时，线性空间中大多数目标更靠近 h，算术均值搜索的线性二分更高效，因此60%-70%的情况算术均值迭代次数更少。
• 当限制目标小于 √(l*h)（即对数空间的中点），且 h/l>10^10 时，目标在对数空间中更靠近 l，几何均值的对数二分能快速收敛，因此>99%的情况几何均值更快。

代码示例 #

function geometric_search(target, high, low)
    current = sqrt(high * low)
    converged = false
    iterations = 0
    eps = 1e-8

    while !converged
        if abs(current - target) < eps
            converged = true
        elseif current < target
            low = current
        elseif current > target
            high = current
        end

        current = sqrt(high * low)
        iterations += 1
    end
    return iterations
end

target = 3.0 
low = 1.0 
high = 1e10

println(geometric_search(target, high, low))

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