昇順に並んだ配列 a[0]〜a[9] = 3, 8, 12, 17, 23, 31, 38, 45, 52, 60 から、二分探索で38を探す。探す範囲を下端 lo = 0、上端 hi = 9 から始め、中央の位置を (lo + hi) ÷ 2 の切り捨てとする。38と比べられる要素の値を順に並べたものはどれか。

正解：C. 23, 45, 31, 38

最初は (0 + 9) ÷ 2 = 4 で a[4] = 23 と比べ、38の方が大きいので lo = 5 にします。次は (5 + 9) ÷ 2 = 7 で a[7] = 45 と比べ、38の方が小さいので hi = 6 にします。次は (5 + 6) ÷ 2 = 5 で a[5] = 31 と比べて lo = 6 とし、最後に a[6] = 38 で一致します。比較は4回で、要素数10の最大回数 ⌊log₂ 10⌋ + 1 = 4 に当たります。31、52、45、38は中央を切り上げにした場合の順で、問題の決め方とは違います。

• A. 23と比べた後は、残りの範囲 a[5]〜a[9] の中央の a[7] = 45 と比べます。
• B. 中央の位置を切り上げで決めた場合の順で、問題の決め方とは違います。
• C. 正しい。a[4]、a[7]、a[5]、a[6] の順に比べ、4回目で見つかります。