algorithm - 如何确定二进制搜索中的边界或迭代次数？

Question

在实现二分搜索时，我们有两种方法来决定何时终止:当搜索空间小于某个预定界限时终止或进行固定次数的迭代时终止。所以我的问题基本上是，如何确定这些边界或我们可以终止算法后的迭代次数。是否有任何预定义的算法或过程？

Answer 1

我想您正在对某个 double 值执行的那种二分查找。因此，您需要尽可能准确，并对迭代次数进行一些限制。

在二分搜索中进行第 i 次迭代后，您剩下的样本空间最多为(高-低)/2^i 大。

现在，根据您希望此值接近的程度，您必须设置 i 的值。

例如:

high = 100000
low = 0

第 30 次迭代后，留给您的样本空间将小至 0.00009313225

这意味着对于此范围，在第 30 次迭代后的最坏情况下，确切位置将相距 0.00009313225 距离。