昇順に整列されたn個のデータが格納されている配列Aがある。
流れ図は，2分探索法を用いて配列Aからデータxを探し出す処理を表している。
a，bに入る操作の正しい組合せはどれか。
ここで，除算の結果は小数点以下が切り捨てられる。
（流れ図：開始→1→lo，n→hi→［(lo+hi)／2→k］→A(k):xを判定（＝ならxは存在する，＜ならa，＞ならb）→aまたはbの後lo:hiを判定（≦ならkの算出に戻る，＞ならxは存在しない）→終了）
正答3
解説
正解は3です。
昇順に並んだ配列に対する2分探索の流れ図を完成させる問題です。
流れ図では、中央の要素A(k)とxを比べ、A(k)<xならa、A(k)>xならbを実行します。
その後、lo≦hiなら探索を続け、lo>hiなら「xは存在しない」と判定します。
【選択肢別解説】
1：× aでk+1をhiに入れると、探索範囲の上限が中央より後ろに広がってしまいます。
A(k)<xなら下限を動かす必要があります。
2：× aでk-1をhiに入れると、xがあるはずの後半を捨ててしまいます。
A(k)<xのとき、xはkより後ろにあります。
3：○ A(k)<xなら、xはkより後ろにあるので、aでk+1をloに入れて後半に絞ります。
A(k)>xなら、xはkより前にあるので、bでk-1をhiに入れて前半に絞ります。
4：× aでk-1をloに入れると、探索範囲がかえって前に広がります。
bでk+1をhiに入れるのも、前半に絞る操作になっていません。
【ポイント】
2分探索では、xが中央より大きければ下限をk+1に、小さければ上限をk-1に更新します。
比較のたびに範囲が半分になるので、比較回数はおよそlog2nです。