アルゴリズムクイックリファレンス 第2版

108

■

5

章 探索

}

}

return false;

}

}

この実装では、

low

,

high

,

ix

という

3

つの変数を使う。

low

は、探索される現在

の部分配列の最小の添字を指す。

high

は、同じ部分配列の最大の添字を指す。

ix

は、

部分配列の中央を指す。このコードの性能は、何回ループを実行するかによって決

まる。

二分探索

は、少々の複雑さを代償にして大きな性能上の利点を得ている。集まり

が、配列のようなメモリ上の単純なデータ構造に貯えられていない場合は、さらに

複雑になる。集まりが大きいときは、ディスク上のファイルのような二次記憶に貯

える必要が生じる。そのような場合には、

i

番目の要素は、ファイル中のオフセット

位置によってアクセスされる。二次記憶を用いると、要素を探索するのにかかる時

間は、記憶装置へのアクセスコストに支配されてしまう。したがって、

二分探索

の

変形である他の解の方が適当かもしれない。

5.2.4

 分析

二分探索

は、ループの実行のたびに、問題のサイズをほぼ半分にする。サイズが

n

の集まりを半分に分ける回数の最大値は、

1

＋



log (n)



となる。

2

つの要素が（イ

ンタフェース

Comparable

で可能なように）等しい、小さい、大きい、のいずれかを

1

つの演算で決定するなら、

1

＋



log (n)



回の比較で済み、

O(log n)

に分類される

性能となる。

メモリサイズ

n

（

n

は

4,096

から

524,288

の範囲）の集まりに貯えられている要素

を確率

p

（

1.0

、

0.5

、

0.0

でサンプルされている） ...