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

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

データの個数が4倍になるということは，2倍になる操作を2回繰り返したことと同じなので，最大探索回数は「2倍になる」のではなく「2回分だけ増える」という関係になります。例えば，データが8個から32個に4倍になった場合，探索回数の目安は3回から5回へと2回増えるイメージです。従って，正解は「イ」です。

「ア」は，1回ではなく2回増えます。「ウ」と「エ」は，2分探索の探索回数はデータ数に比例して増えるのではなく，log（対数）の関係で増えるため，データ数が4倍になっても探索回数が2倍や4倍になるわけではありません。