データの個数が8倍に増加した場合,二分探索の最大探索回数に関して最も適切なものはどれか。
① 2回増加する。
② 3回増加する。
③ 8回増加する。
④ 約3倍に増加する。
⑤ 約8倍に増加する。
答え
②
解説
二分探索は、データを半分に分け、どちらに目的のデータが含まれているかを判定し、これを繰り返す、という検索方法です。
つまり、データ量が2倍になれば、検索回数は1回増え、データ量が4倍(2倍の2倍)になれば2回、データ量が8倍(2倍の2倍の2倍)になれば3回増えます。