中小企業診断士 第1次試験 ハードウェア・ソフトウェア・アルゴリズム 練習問題 第11問: 昇順に整列された1,000件のデータの中から、2分探索法で目的のデータを探す。目的のデータが見つかるか、無いと分かるまでの比較の回数の最大として、最も適切なもの

「10回」が適切です。2分探索法は、整列されたデータの中央の値と目的の値を比べ、目的の値が中央より小さいか大きいかで探す範囲を半分に絞ることを繰り返す方法です。

比較を k 回まで行えば、2の k 乗から1を引いた件数までのデータを探しきれます。2の9乗−1＝511件では1,000件に足りず、2の10乗−1＝1,023件なら1,000件を含むので、比較の回数の最大は10回です。

「9回」は、2を何乗すると1,000になるか（およそ9.97乗）の小数を切り捨てただけで、最後の1回の比較を数え落とした値です。「500回」と「1,000回」は、先頭から順に1件ずつ比べる線形探索法の平均（およそ件数÷2）と最大（件数そのもの）の回数です。

「32回」は1,000の平方根（およそ31.6）から出した値で、2分探索の回数とは関係がありません。データの件数が2倍になっても2分探索の最大の比較回数は1回しか増えないことが、線形探索法と比べた強みです。

2分探索法はデータが整列済みであることが前提で、最大の比較回数は「2のk乗−1が件数以上になる最小のk」です。