我有一个问题，我的二进制搜索算法找到2的平方根似乎是在一个无限循环并永远运行：
num = 2
low = 1
high = num
i = 0
while((i**2) != 2): #was while(low<high): but wasnt working with it either
i = low + (high - low) / 2;
sqrt = i * i
if (sqrt == num):
print(i)
elif(sqrt < num):
low = i
else:
high = i
print(sqrt)
testRoot = 2 ** (.5)
print(testRoot)
我不确定我的while循环是否存在问题。我认为这将是一个非常直接的二进制搜索算法，稍作修改以适应平方根方面。
在运行我的代码时，我似乎无法让它产生任何输出。我不确定代码或编译器是否存在真正的问题，因为我认为我的算法与我过去的算法非常接近。
问题是using == on floating point numbers几乎总是一个不好的做法，并且有关于它的various问题。你应该用abs(a - b) < precision替换比较。另请阅读此问题下的评论，非常有用。
我修改后的代码看起来像这样（Python 3），如果你想要更高的精度，用更小的数字替换1e-6。但请注意，“太精确”并不明智，如果您希望循环停止，建议使用1.0e-15或更大的精度，因为浮点数本身具有精度限制。
num = 2
low = 1
high = num
i = 0
while abs((i**2) - num) > 1e-6: # Note
i = low + (high - low) / 2
sqrt = i * i
if abs(sqrt - num) < 1e-6: # Note
print(i)
elif(sqrt < num):
low = i
else:
high = i
print(sqrt)
testRoot = 2 ** (.5)
print(testRoot)
正如在my original comment和所有答案中所提到的，square root of 2是irrational。不是完美正方形的每个整数的平方根对于那个问题是不合理的，因此在这方面2并不特别。重要的是x**2 == 2永远不会对任何有限精度的x都是正确的（因为有限精度是说数字是理性的另一种方式）。
其他答案建议搜索，直到达到一些固定的，预先确定的准确度。这很有效，特别是如果您提前知道答案的二进制数量级，那么您可以将结果的准确度设置为最后一位数。
我想建议一个更自然的方法。您可以检查您的中心值是否恰好等于其中一个边界。这意味着边界之间的差异的一半表示当前猜测的精度不到一位数。你对中心的描述已经是正确的：i = low + (high - low) / 2可以使用low与high和==进行比较，而i = (low + high) / 2可能不会。这是因为high - low的精度大于或等于任一界限的精度，而low + high可能会丢失一些数字。
所以这是我建议的：
num = 2
low = 1
high = num
guess = low + (high - low) / 2
count = 0
while guess != low and guess != high:
sqr = guess * guess
if sqr == num:
break
elif(sqr < num):
low = guess
else:
high = guess
guess = low + (high - low) / 2
count += 1
else:
if abs(low * low - num) < abs(high * high - num):
guess = low
else:
guess = high
print(count, ':', sqr)
print(num ** (.5), '~=', guess)
我添加了count进行验证。结果在52次迭代中获得，精度在1位精度内：
52 : 2.0000000000000004
1.4142135623730951 ~= 1.4142135623730951
对边界的最终检查（else的while子句）确保您获得与所需结果最接近的结果，无论您首先击中哪一个。
收敛是正确的：64-bit floating point number in IEEE-754 format在尾数中有53位，所以你必须将你的搜索空间精确地减半才能得到你的结果（第一次在循环之外）。
这是我用于测试的片段：https://ideone.com/FU9r82
两个浮点数之间的相等是非常严格的条件，因为2的平方根在小数点后具有无限数字。试试这个while条件：
while (abs((i ** 2) - 2) > 1e-8)
进行一些探索通常很有帮助。
$ python
Python 3.6.6
>>> import math
>>> import numpy
>>> import scipy
>>> import numpy
>>> math.sqrt(2) ** 2
2.0000000000000004
>>> numpy.sqrt(2) ** 2
2.0000000000000004
>>> scipy.sqrt(2) ** 2
2.0000000000000004
>>> (2.0**(0.5))**2
2.0000000000000004
>>> x = math.sqrt(2) ** 2
>>> math.sqrt(x)
1.4142135623730951
>>> math.sqrt(2)
1.4142135623730951
>>> x*x
4.000000000000002
>>> x**2
4.000000000000002
>>> 1.414213562373095**2
1.9999999999999996
>>> 1.41421356237309505**2
2.0000000000000004
>>> 1.41421356237309505
1.4142135623730951
>>> 1.41421356237309504
1.4142135623730951
>>> 1.41421356237309504**2
2.0000000000000004
>>> 1.41421356237309503**2
1.9999999999999996
>>> 1.41421356237309503 * 1.41421356237309504
2.0
>>> 1.41421356237309504 - 1.41421356237309503
2.220446049250313e-16
一点点肘部油脂可以教育。 （而且令人困惑！）
让我们来看看错误
>>> s =set()
>>> exact = 0
>>> exact_over = 0
>>> exact_under = 0
>>>for i in range(100):
... differ = (i - (i**0.5)**2)
... s |= {differ}
... exact += 1 if differ == 0 else 0
... exact_over += 1 if differ > 0 else 0
... exact_under += 1 if differ < 0 else 0
>>> sorted(list(s))
[-1.4210854715202004e-14,
-7.105427357601002e-15,
-3.552713678800501e-15,
-1.7763568394002505e-15,
-8.881784197001252e-16,
-4.440892098500626e-16,
0.0,
4.440892098500626e-16,
8.881784197001252e-16,
1.7763568394002505e-15,
3.552713678800501e-15,
7.105427357601002e-15,
1.4210854715202004e-14]
>>> exact_under, exact, exact_over
(26, 49, 25)
正如其他几篇文章所述，比较i * i == 2无法奏效。
设计停止标准的简单解决方案是告诉您需要多少精度。实际上，在二分法搜索中，精确比特的数量在非常迭代时增加一。
因此，对于完全双精度精度，迭代53次（更多是没用的）。另请注意，在循环内测试相等性会适得其反。
num= 2
low= 1
hig= 2
for i in range(53):
mid= 0.5 * (low + hig)
if mid * mid < num:
low= mid
else:
hig= mid
print(mid)
这里53次迭代是合适的，因为初始估计对于第一位（1≤√2<2）是准确的。对于不太准确的初始估计，请添加一些迭代。