python - 类二进制搜索

Question

这是一个理论问题。

exercise from leetcode作为基础。

我的任务解决方案是二分搜索。但问题不在于它。

我发现完美的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”改编为整数算术。这反过来又可以被看作是牛顿寻找方程根的更通用方法的一个实例。

在此代码中，保留不同的 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。此方法大约使每次迭代的“好位”数量加倍，因此猜测越接近最终结果，效率就越高。