バイナリサーチの戻り値にleft < rightの条件は必要か

Question

見ている本にバイナリサーチが以下のように実装できると書いてあるのですが、return文のleft < rightの記述が必要な理由がわかりません。試しにreturn array[left] == value;と記述して配列にある探している値がある場合とない場合をテストした所正しく動作しているので若干困惑してます。

bool bsearch(const int array[], int left, int right, int value) {
    while (left + 1 < right) {
        int med = (left+right) / 2;
        if (array[med] > value) right = med;
        else left = med;
    }   

    return left < right && array[left] == value;
}

Answer 1

right - left は検索する要素の数になります。これが 0 以下の場合に False を返しています。
もしこの条件が無かった場合、範囲外のメモリを参照してたまたまそこにあったデータが探している値と同じだった場合に True が返ってしまうバグになります。

Comments

[ijuya_yika]

なるほどです。御回答ありがとうございます。

Answer 2

おそらく、昇順にソートされたarray配列のleftからrightまでの範囲でvalue値があるかどうかを見ている関数だと思われますが、
この関数の引数が、left>=right の場合にどういう結果を返すのか考えてみましょう

Comments

[ijuya_yika]

なるほど。ではleft<rightは異常終了を防ぐ為…ということでしょうか？

[y_waiwai]

それはこの関数を使う処理がどういうことをしているか、によります
おそらく、その処理中でleft>=rightのときにはFALSEを返すべし、という仕様なんだろう。
というとこらへんなんでしょうね

[ijuya_yika]

なるほどです。御回答ありがとうございます。

Answer 3

解決済みですが、

この引数のrightは配列内の添字ですか？左端は境界を含み、右端は境界を含まない非対称な添字を想定していると思います。

右端で要素を見つけた場合の分岐に見えます。

Comments

[ijuya_yika]

コメントありがとうございます。はい、仰るとおり[left, right)の境界です。
右端の要素を見つけた場合while(l+1<r)で対処されているのかなーと思ったのですがどうでしょう。

[HogeAnimalLover]

はい。基本はループ条件だけで分岐が成立すると思います。

ただ、元の配列の右端、つまりrightの初期位置で検索がヒットする場合を例外的に扱う必要があるはずです。

[Zuishin]

戻り値は left の位置の要素とターゲットを比較しています。
left == right の場合は right の位置と言えますが、left > right の場合は違うのではないでしょうか？