二分探索は、配列内の要素を見つけるだけでなく、方程式の根や単調 (増加または減少) 関数の値を見つけるためにも使用できます。
単調関数 f とこの関数の値 C を与えてみましょう。 \(f(x)=C\) となる、この関数の x 引数の値を見つけます。
単調増加関数の例:
関数の値が指定された値より正確に大きく、正確に小さいような境界を選択します。このセグメントの中央の値を選択しましょう。指定された値より小さい場合は、左の境界線をセグメントの中央に移動します。それ以外の場合は、右側の境界線を移動します。次に、境界を狭めるプロセスを繰り返します。しかし問題は、いつ検索をやめるかということです。続きを読む こちら。
たとえば、数値 x の平方根を求める問題を考えてみましょう。 x の平方根 (\(\sqrt x\) で示される) は、次のような数値 y です。 \(y^2 = x\).
次のように問題を定式化してみましょう。与えられた実数 x ( \(x >= 1\)) に対して、ドット以降 5 文字以上の精度の平方根。
検索するセグメントの境界線を選択する
無限の数値全体をチェックすることはできないため、ルートの検索の境界を定義する必要があります。まず、左側の境界線を見つけて、任意の負の点 (例: -1) を選択します。その値が指定された値より大きくなるまで、それを 2 倍にします。正しい境界線を見つけるために、任意の正の点 (例: 1) を選択します。この時点の関数の値が指定された値より小さくなるまで 倍にしていきます。
または、検索の境界が正確にわかっている場合は、左側の境界として 1 を取得し、数値そのものを x とすることもできます。 その後、現在のセグメントを半分に分割し、中央を正方形にし、それが x より大きい場合は上面を置き換えます。それ以外の場合は、上面を置き換えます。下
に。
最終実装:
どこ で？
eps - 解を求める精度。
x - 平方根を求める指定された数値、
m - アルゴリズムの実行後に 結果が保存される番号。
|