技術士 第一次試験 基礎科目 2群 情報・論理 練習問題 第3問: 昇順に整列済みの 2,048 件のデータから、ある値を 2 分探索で探す。1 回の比較で、探す値が探索区間の中央の要素と一致するか、それより大きいか小さいかが分

「12 回」が適切です。2 分探索は整列した配列で区間を半分ずつに絞る探索で、比較の回数は O(log n) です（NIST Dictionary of Algorithms and Data Structures「binary search」）。

1 回比較して一致しなければ、中央の要素を除いた片側に区間を絞るので、残る区間の要素数は最も多くて ⌊n/2⌋ 個です。

2,048 → 1,024 → 512 → 256 → 128 → 64 → 32 → 16 → 8 → 4 → 2 → 1 → 0

要素の残る区間ごとに 1 回比較し、最大 12 回です。式では ⌊log₂ n⌋＋1 で、2¹¹＝2,048 より 11＋1＝12 回です。

「11 回」は log₂ 2,048＝11 で、区間が 1 件になったときの最後の比較を落とした値です。「24 回」は一致と大小を別々の比較として 1 段で 2 回ずつ数えた値ですが、ここでは 1 回の比較で両方が分かります。

「1,024 回」は n/2 で線形探索の平均のおよその件数、「2,048 回」は先頭から順に調べる線形探索の最大の回数です。