二分查找技术疑问：为何设置high为0会导致程序死循环？

以下是你提供的二分查找求立方根的代码：

low = 0.0
high = x  # This is the square root we are trying to find 
ans = (high + low) / 2  # Here we take half of the range between 1 and 25

while abs(ans**3 - x) >= epsilon:
    print("low = " + str(low) + " high =" + str(high) + " ans = " + str(ans))
    # Note here if the gap is bigger than epsilon, this means the answer has not been found yet, we want to see what
    # the low and the high are 
    numGuesses += 1
    if x > 0 :
        if ans**3 < x :
            low = ans  # Note here although we set that >0.01 as answer has been found, we need it to rinse and repeat the process 
                      # of halving , when tis too small, the low become ans, which means we take away the lower half
        else:
            high = ans  # This is when ans**2 > x , which has gone too far, hence we take away the higher halve
        ans = (high + low)/2
        # We see this entire loop, only breaks if abs(ans**2 - x) < epsilon, which mean its close enough 
        
    else :
        if ans**3 > x :
            low = x
            high = ans
        else:
            low = ans
            high = 0  # 修改后这里设为0，原代码是1
            # Note here it cannot be 0

        ans = (high + low) / 2 

print("number of guess is " + str(numGuesses))  
print(str(30000 - numGuesses)+" times less run than Guess and check.")
print(str(ans) + "is close to square root of" + str(x))

死循环原因分析 #

核心问题出在x∈(-1,0)的场景下，修改后的代码无法覆盖真实立方根所在的区间，导致搜索值永远无法满足收敛条件：

• 当x是介于-1和0之间的负数时（比如x=-0.125），真实立方根ans₀满足ans₀³=x，且ans₀ <x（因为立方根函数单调递增，x∈(-1,0)时x³ >x，所以ans₀³=x <x³ → ans₀ <x）。
• 代码初始搜索区间是[0, x]（因为low=0.0，high=x且x<0），这个区间里的所有数都大于x。当修改high=0后，后续的搜索区间只会在[x, ans]或[ans, 0]之间调整，始终无法扩展到x左侧（更小的负数区域）。
• 而区间内所有大于x的负数（∈(x,0)），它们的立方值都大于x（因为a∈(-1,0)时，a³ >a，且a >x → a³ >a >x），所以abs(ans³ -x)始终等于ans³ -x，这个值会趋近于x³ -x（大于0），永远无法小于设定的epsilon，循环因此陷入死循环。

为什么设high=1时部分场景正常 #

当你设置high=1时，如果测试的是x≤-1的负数（比如x=-8），真实立方根ans₀（比如-2）会落在[x,1]区间内，代码的区间调整逻辑能逐步逼近真实值，所以程序可以正常结束。但如果测试的是x∈(-1,0)的负数，high=1同样无法扩展搜索区间到x左侧，程序依然会陷入死循环——你之前测试正常只是刚好选了≤-1的x值。

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