プログラミング作法 第２章 アルゴリズムとデータ構造 ２．１ 探索

不慣れな分野のプログラムを開発しようとするなら、その分野ですでにどんなことが解明されているのかを調べてみなければならない。さもないと、優れた手法がすでに存在するのに、自己流の下手なやり方を考案するのに時間を無駄にするはめになるからだ。

　この探索アルゴリズムは、個々の要素を順番に調べていって希望の要素かどうかを判断することから、逐次探索(sequential search)と呼ばれる。逐次探索はデータ量が少ないときには十分高速だ。

　逐次探索は簡単だが、作業量は探索対象のデータ量に直接比例する。要素の数が倍になれば、希望の要素が存在しないときには探索時間も倍になる。これは線形の関数なので(実行時間がデータサイズの１次関数になる)、この手法は線形探索(linear search)とも呼ばれている。

このような大きめの配列の場合には、二分探索(binary search)を使ったほうが効率的だ。二分探索アルゴリズムは、我々が辞書で単語を引く方法を整然と実行するバージョンと言えるだろう。まず真ん中の要素をチェックする。その値が自分の探している値よりも大きかったら前半を調べ、小さければ後半を調べる。そして希望の項目がみつかるかそれが存在しないと判断できるまで、この手順を繰り返せばいい。
　二分探索を実行するには、上の例のように表がソートされていなければならない。また、表の長さもわかっていなければならない。

ある入力サイズ(個々の実装による)を超えると、線形探索よりも二分探索のほうが高速になる。