二分探索内に 2 つの比較がありますが、2 つの下層の間で正確な優先順位を設定することはできません。以下の 2 つのサンプルの間で振動します。
for (int step = 0; step < 100; ++step) {
double middle = (left + right) / 2;
if (f(middle) > 0) right = middle; else left = middle;
}
と
for (int step = 0; step < 100; ++step) {
double middle = (left + right) / 2;
if (f(middle) > eps) right = middle; else left = middle;
}
f は単調増加関数です。これは、eps が小さい場合でも、二分探索パラメーターの対応するエラーがはるかに大きくなる危険性があるためです。一方、丸め誤差が原因で等しい値の比較が正しくない場合でも、等しい値が 1 つのポイントにしか表示されず、それに非常に近いポイントではすべてが正しいため、二分探索は正しく収束します。それについて考えたいと思います。