タイトルが完全ではないために尋ねたいものがクリアされないことがあります(タイトルは150語に制限されています)。バイナリサーチは、アルゴリズムで使用される3つの変数の1つがキーの正しい位置を保持することを保証しますか?
私の質問は、バイナリサーチでは、アルゴリズムで使用される3つの変数の1つが、ソートされたシーケンスの中に見つからなかったとしても、キーの正しい位置を保持することを保証していますか?
質問を明確にする例があります。
長さ5のソート済み配列Aを考えてみましょう。
int a[] = {2, 8, 9, 11, 14};
明らかに、配列は、シーケンスを見ることによって7が含まれていない、我々は、配列の場合、要素7は、インデックス1を与えられているだろうと言うことができます。
上記のシーケンスでキー7を使用してバイナリ検索を実行すると、-1が返されます(これは実装に依存します)。しかし、p(pよりも大きくなるとループを破る)、q((p + r)/ 2を格納する)、r(p未満になるとループを壊す)という3つの変数のいずれかが、ループが壊れたときに上記のシーケンスの値7の正しい位置(1)を保持しますか?
または、数学的計算によって7の正しい位置を見つけることができますか?