背景：在数组上进行二进制搜索时，我们初始化上h和下l界，并在它们之间的中点(算术平均值)进行测试m:=(h+l)/2。然后，我们要么改变上界，要么改变下界，并迭代到收敛。
问题：我们可以对(无界)实数使用类似的搜索策略(以及它们的浮点近似)。我们可以使用收敛的容差来终止搜索。如果搜索范围在正实数上(0<l<h)，我们可以取几何平均值m:=(hl)^.5。我的问题是，几何平均值什么时候更快(需要几次迭代才能收敛)
动机：当我尝试对一个连续变量进行二进制搜索时，出现了这种情况，其中初始边界非常宽，需要多次迭代才能收敛。我可以在二进制搜索之前使用指数搜索，但我对这个想法很好奇。
我尝试了什么：我试图通过选择一百万个介于2和我选择的初始h之间的随机(浮点)数字来了解这一点。我保持初始l=1固定，目标必须在10^-8的公差范围内。我在10^1和10^50之间变化了h。算术平均值在大约60-70%的情况下具有较少的迭代。
但几何平均值是偏斜的(低于算术平均值)。因此，当我将目标限制为小于初始边界sqrt(lh)的几何平均值时(仍然保持l＝1)，对于大的h>10^10.因此，似乎h和目标/h的比率都可能涉及迭代次数。
代码示例：这里有一个简单的Julia代码来演示：
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))
这个问题的核心是"几何平均二进制搜索的速度有多快">
在n个离散元素之间的普通(算术平均)二进制搜索中，步数为s=log2n(在大的n极限中)。在连续的情况下，如果我们在大小为R的较大区间中搜索大小为d的区间，则步长为s=log2(R/d)。
现在考虑连续情况，但使用几何平均值。我们在连续变量x上搜索较大区间[l，h]中的区间[k，k+d]，我们的第一个检验将是(lh)1/2。现在我们"取整个问题的日志"；，也就是说，我们换成一个新的变量y，它被定义为ln(x)。所以现在我们在较大的区间[ln(l)，ln(h)]中搜索区间[ln这是y中的算术平均二进制搜索，但目标的大小因其位置而异步骤数将为
s=log2((ln(h)-ln(l))/(ln(k+d)-ln
注意，ln((k+d)/k)=ln(1+d/k)。
因此，找到目标的步骤数取决于k，即目标的位置。距离较低端的目标会更大，因此会比距离较高端的目标更快地被发现。在低端附近，几何平均搜索比算术平均快，在高端附近，算术平均比几何平均快。
那么，关键点在哪里呢？算术平均搜索和几何平均搜索什么时候会同样快？我们将步数设置为相等：
log2(ln(h/l)/ln(1+d/k))=log2
并求解k:
ln(1+d/k)=d ln(h/l)/(h-l)
1+d/k=(h/l
(这似乎是正确的，但我还没有写代码来测试它。)
当每个决策将"；可能的答案"；对半
因此，对于在阵列中进行搜索，在这方面，每次测试可能范围的中心是最佳的。
如果你没有在数组中搜索，那么这取决于你的停止条件。在您的情况下，您正在搜索所有可能的浮点值中的平方根。
如果你的停止标准是一个绝对差，，这就是你写的，那么在最坏的情况下，选择可能范围的算术平均值仍然是最好的。
然而，如果你的停止标准是百分比差异，那么还有更多的"；"小"；答案比大答案(你知道我的意思)。这是在搜索答案的日志时使用绝对差异标准。在这种情况下，几何平均数在最坏的情况下是最优的。
如上所述，您编写了一个绝对差停止条件，但这被浮点数表示的细节所混淆。浮点数表示为2em，其中e和m是精度有限的整数。因此，即使你编码了一个绝对差停止条件，小答案也比大答案多，所以几何平均值可能会更好。
这就解释了为什么几何平均值可能更适合您的具体实施。。。但我担心，对于某些非常大的输入，您的实现将无法收敛。