データの探索回数

◆線形探索法
　　データ数がＮの時
　　平均探索回数・・・・・（Ｎ＋1）÷２
　　最大探索回数・・・・・　Ｎ

◆２分探索回数
　　データ数がＮの時
　　平均探索回数・・・・・ｌｏｇ（2）Ｎ
　　最大探索回数・・・・・ｌｏｇ（2）Ｎ＋１

★★★宿題：二種向け★（2000/2/4）

　２分探索において，整列されているデータの個数が４倍になると，最大探索回
数はどうなるか。

　ア　１回増える。

　イ　２回増える。

　ウ　約２倍になる。

　エ　約４倍になる。

解答例

２分探索の最大探索回数は上記の公式より

ｌｏｇ（2）Ｎ＋１
データ数が４倍になるから
　　ｌｏｇ（2）（Ｎ×４）＋１
　　　　　　　↓
　　　　この部分の計算はＮ進数の桁数の計算を参照

＝ｌｏｇ（2）Ｎ＋ｌｏｇ（2）２＾２＋１
＝ｌｏｇ（2）Ｎ＋２ｌｏｇ（2）２＋１
＝ｌｏｇ(2)Ｎ＋２＋１
となり、２回増えることになる