バイナリ検索終了条件

Question

バイナリ検索を繰り返し実行するときは、いつもwhile (low < high)またはのどちらを使用すべきかを常に混乱させています。

どちらも機能しますが、誰かが実際の利点を他のものよりも教えてくれますか？

Answer 1

あなたがリストしている2つの終了条件は、低値と高値が包括的か排他的かに応じてしばしば使用されます。境界が包括的である場合、低=高の場合、チェックする配列に1つの要素が残っており、内側のループは別の時間に実行する必要があります。したがって、低い≤が適切かどうかのテストが適切です。一方、低い値が含まれ、高い値が排他的である場合、低い=高いときにすべての要素を使い果たしたので、低い値の形式のテストがより適切です。