平成23年度 秋期 午前 問8

✓ これが正解イleft ≦ right

解説

範囲が一つに縮んだときも調べに行きます。

2分探索の流れ図で、繰り返しを続ける条件の片方を選ぶ設問です。条件は二つを同時に満たす間だけ繰り返す形になっており、前半はまだ見つかっていないことを表しています。ですから空欄が受け持つのは、まだ調べる範囲が残っているという条件です。範囲は左端と右端の二つの変数で表されています。この区間に含まれる要素の個数は、右端から左端を引いて 1 を足した数です。要素が一つでも残っている状態は、この個数が 1 以上のとき、つまり左端が右端以下のときです。分かれ目は等号を含めるかどうかの一点になります。等号を落とすと、範囲が一つに縮んだ時点で繰り返しを抜けてしまい、その一つを調べないまま終わります。探している値がちょうどそこにあった場合、配列の中にあるのに見つけられません。反対に、等号を含めても繰り返しが止まらなくなる心配はありません。比較のたびに左端が中央の次へ進むか、右端が中央の手前へ下がるかのどちらかが必ず起こるので、範囲は毎回一つ以上狭まり、いつか左端が右端を追い越して条件が偽になります。

ほかの選択肢はなぜ違うのか

• アleft ＜ right：等号を落とした形です。要素が二つの配列で後ろ側の値を探すと、左端と右端が同じ値になった時点で繰り返しから抜けてしまい、配列に確かにある値を見つけられないまま終わります。
• ウleft＋1 ＜ right：左端に 1 を足したうえで等号も落としているので、残りが二つになった段階で繰り返しが終わります。調べ残す要素が二つぶんに増えるため、取りこぼしはさらに大きくなります。
• エleft＋1 ≦ right：左端に 1 を足した形です。残りが一つになったところで条件が偽になるため、最後の一つを調べないまま抜けるという同じ取りこぼしが起こります。境界を 1 ずつずらして試させる並びです。