基本情報技術者試験 - 令和5年12月修了 - 問6

答え ： イ
分野 ： テクノロジ系 › 基礎理論 › アルゴリズムとプログラミング › アルゴリズム
解説 ：
「2分探索」（二分探索）とは，あらかじめ並べ替えられたデータの中から，探索範囲を半分ずつに絞り込んでいくことで，目的のデータを効率よく見つけ出す方法です。データの個数がN個のとき，2分探索の最大探索回数は，おおよそ2を底とするNの対数（log₂N）に比例することが知られています。

データの個数が4倍になるということは，Nが4Nになるということですが，この場合，log₂(4N)はlog₂N＋log₂4，つまりlog₂N＋2と表すことができます。これは，元の最大探索回数（log₂Nに相当する部分）に対して，2回分だけ増えるということを意味しています。したがって，データの個数が4倍になっても，最大探索回数は2回増えるだけで済み，正解は「イ」です。

「ア」の「1回増える」は，データの個数が2倍になった場合の増え方であり，4倍の場合には当てはまりません。「ウ」の「約2倍になる」，「エ」の「約4倍になる」という説明は，探索回数がデータの個数に比例して増えるかのような誤解に基づくもので，実際には対数的にしか増えないという2分探索の効率の良さを正しく捉えていません。