昇順に整列された n 個のデータが格納されている配列 A がある。流れ図は， ２分探索法を用いて配列 A からデータ x を探し出す処理を表している。 a, b に入る操作の正しい組合せはどれか。ここで，除算の結果は小数点以下が切り捨てられる。
| ａ | ｂ | |
|---|---|---|
| ア | k+1→ hi | k-1→ lo |
| イ | k-1→ hi | k+1→ lo |
| ウ | k+1→ lo | k-1→ hi |
| エ | k-1→ lo | k+1→ hi |
昇順に整列された n 個のデータが格納されている配列 A がある。流れ図は， ２分探索法を用いて配列 A からデータ x を探し出す処理を表している。 a, b に入る操作の正しい組合せはどれか。ここで，除算の結果は小数点以下が切り捨てられる。
| ａ | ｂ | |
|---|---|---|
| ア | k+1→ hi | k-1→ lo |
| イ | k-1→ hi | k+1→ lo |
| ウ | k+1→ lo | k-1→ hi |
| エ | k-1→ lo | k+1→ hi |
正解： ウ
解説：
２分探索法は、整列されたデータの中央の値と対象データを比較し、 それより前方にあるか後方にあるかを判断する。
前方にデータがある場合は、前半分のデータの中央のデータと比較し、 後方にデータがある場合は、後半分のデータの中央のデータと比較する。
この操作を繰り返すことによって、検索する方法である。
a,bの直前でA(k) と x を比較しているが、それによって「等しいければｘは存在する」「A(k) は x より小さいので、ｘはそれより後にある」「A(k) は x より大きいので、ｘはそれより前にある」のいずれかが分かる。
これを踏まえて空欄を埋める。
A(k) の方が小さいときは、ｘはそれより後にあるので、次は後ろ半分を探すことになる。よって、k+1 を lo に入れれば、A(k) の次の要素を先頭にした後ろ半分が次の検索範囲となる。
逆に A(k) の方が大きいときは、ｘはそれより手前にあるので、次は前半分を探すことになる。よって、k-1 を hi に入れれば、A(k) の手前の要素を末尾にした前半分が次の検索範囲となる。