二进制搜索

Question

这是理论问题。

我的任务解决方案是二分查找。但问题不在于此。

我在“讨论”选项卡上找到了完美的 solution。

（下一个代码已从那里获取）

class Solution:
    def mySqrt(self, x: int) -> int:
        low, high= 1, x
        while low<high:
            high = (low + high) // 2
            low = x // high

        return high

效果很好。我的问题是：

对于常规的二进制搜索，我们取序列的中间部分，并根据比较结果删除多余的部分（左侧或右侧），然后重复直到结果。

这个实现基于什么？

此解决方案从开始的中间部分和小部分之后切掉部分序列。

Answer 1

此代码不是基于二进制搜索。相反，它基于将古老的“Babylonian method”改编为整数运算。这反过来又可以看作是对牛顿 more-general 求方程根方法的一个实例的预期。

保持不同的 low 和 high 变量在此代码中并不重要。例如，更常见的编码方式是：

def intsqrt(n):
    guess = n  # must be >= true floor(sqrt(n))
    while True:
        newguess = (guess + (n // guess)) // 2
        if guess <= newguess:
            return guess
        guess = newguess

但更仔细地寻找更好的初始猜测。

顺便说一句，二分搜索每次迭代都会将“好位”的数量增加 1。这种方法大约 使每次迭代的“好位”数量增加一倍 ，因此猜测越接近最终结果，效率就越高。

Answer 2

虽然巴比伦人知道这种方法，但这种方法很微妙（请参阅 Tim 的回答）。

假设 h > √x。然后

l = x/h < √x 和
(l+h)/2 > √x.

第一个属性很明显。第二，观察 1. 和 2. 暗示 x+h² > 2h√x 或 (h-√x)^2 > 0，这是正确的。

所以h保持在√x之上，但越来越近（因为(l+h)/2 < h）。当使用整数进行计算时，有一个时刻 l≥h.

这个方法是怎么被发现的？

假设您有 √x 的近似值 h，我们想改进它，并进行修正 δ。我们写x = (h-δ)² = h²-2hδ + δ² = x。如果我们忽略δ²，那么我们绘制h-δ = (h²+x)/2h = (h+x/h)/2，也就是我们的(h+l)/2.

二进制搜索

Binary-like search

python

algorithm

search