二分探索の比較回数
昇順に整列された 1000 個の異なるデータの中から，二分探索法によって目的のデータを探索する。探索キーと中央の要素との 1 回の比較で一致・大小を判定できるものとするとき，最大の比較回数はどれか。
- ア9
- イ10
- ウ500
- エ1000
正解と解説を見る
正解 イ
この問題の基礎知識
- 二分探索は，整列済みのデータの中央の要素と探索キーを比較し，探索範囲を半分ずつ絞り込む方法である。データが整列されていることが前提となる。
- 1 回の比較で一致・大小を判定する場合，k 回の比較で探索できるデータは最大 2 の k 乗−1 個であり，n 個のデータの最大比較回数は ⌊log2 n⌋＋1 回となる。
- 線形探索（逐次探索）は先頭から順に比較する方法で，最大比較回数は n 回，目的のデータが存在する場合の平均比較回数は約 n÷2 回である。二分探索の比較回数は log2 n に比例する。
ア9
9 回の比較で探索できるのは最大 2 の 9 乗−1＝511 個までである。1000 個のデータでは 9 回で目的のデータに到達できない場合があるので，最大回数としては足りない。
イ10正解
二分探索では 1 回の比較ごとに探索範囲がほぼ半分になり，k 回で最大 2 の k 乗−1 個を探索できる。511＜1000≦1023 なので最大比較回数は 10 回（⌊log2 1000⌋＋1）である。
ウ500
500 は線形探索（逐次探索）で目的のデータが存在する場合の平均比較回数（約 n/2）に相当する。二分探索の比較回数は log2 n のオーダであり，はるかに少ない。
エ1000
1000 は線形探索で先頭から順に比較した場合の最大比較回数（n 回）である。二分探索では範囲を半分ずつ絞り込むので，最大でも 10 回で済む。
検証用の出典出典照合済み
IPA 応用情報技術者試験（レベル 4）シラバス照合の根拠（1 件）
- イ（正解）: 2 分探索法・線形探索法は出題範囲（用語例に線形探索法，2 分探索法）
整列のアルゴリズム，併合のアルゴリズム，探索のアルゴリズムを理解する。
IPA 応用情報技術者試験シラバス Ver.7.2 · 中分類2 アルゴリズムとプログラミング 2. アルゴリズム ① 整列・併合・探索のアルゴリズム（新しいタブで開きます）
検算: 1 回の比較で範囲が半分になり，k 回で最大 2^k−1 個を探索できる。2^9−1＝511＜1000≦2^10−1＝1023 なので最大 10 回（⌊log2 1000⌋＋1＝9＋1）。線形探索の最大は n＝1000 回，存在する場合の平均は (n＋1)/2≒500 回。一般的な数学（対数・数え上げ）なので出典不要。