基本情報技術者試験基礎・応用
条件を読む・根拠を説明する
境界を探す二分探索
条件を整理し、答えを選んでから解き方を確認しましょう。
A=[2,4,4,7]、添字0〜3。lo←0,hi←4。lo<hiの間m←床((lo+hi)/2)、A[m]<4ならlo←m+1、他はhi←m。終了時loはどれか。
答え・解き方を読む
1
図で見る
候補区間を半分へ絞り続ける
図を拡大して見る ↗整列済みという前提で中点と比較し候補を狭めます。境界探索のlo/hiはどちらを含むかを設問のコードで確認します。単に添字から位置を計算する問題では、この図を使いません。
図は問題の関係を整理する模式図です。記号には各問題の数値を当てはめます。寸法・面積・時間の縮尺や、実施工の全条件は表していません。
考える順序
- 1初回m=2でA[2]=4なのでhi=2
- 2次はm=1でhi=1、次はm=0でlo=1
- 3lo=hi=1で最初の4の位置に止まる
選択肢ごとの理由
- 比較 · 4
4は配列末尾の次で最初の一致位置ではありません。
- 正解 · 1
初回m=2でA[2]=4なのでhi=2。次はm=1でhi=1、次はm=0でlo=1。lo=hi=1で最初の4の位置に止まる。
- 比較 · 2
一致した中央で即終了する処理ではありません。
- 比較 · 3
7の位置より前に条件を満たす要素があります。