二分查找和 eps 比较

Question

我在二分搜索中进行了两次比较，但我无法在两个底层之间做出准确的偏好。我在下面的两个样本之间振荡：

for (int step = 0; step < 100; ++step) {
  double middle = (left + right) / 2;
  if (f(middle) > 0) right = middle; else left = middle;
}

f

for (int step = 0; step < 100; ++step) {
  double middle = (left + right) / 2;
  if (f(middle) > eps) right = middle; else left = middle;
}

是一个单调递增函数，因为即使 eps 很小，二分搜索参数中的相应误差也存在更大的危险。另一方面，即使由于舍入误差而导致我们对相等值的比较不正确，二分搜索仍将正确收敛，因为相等值可能只出现在一个点中，并且在非常接近它的点中所有内容都将是正确的。我想对此有一个想法。

Answer 1

从您的代码来看，您正在尝试决定函数何时具有零值。第一种方法已经足够好了，因为它符合你的意图。看来没有必要用第二种方法了。