サーチ（探索）とは、右図のような配列ａがあるとき、与えた値ｘと同じ値をもつ要素ａ[ｉ]を探し、その要素番号を求める操作です。
例えば、ｘ＝５０ならばｉ＝５となります。また、ｘ＝３５のときは一致する要素が存在しないことになります。
ａ[ｉ]の学籍番号に対応した学生氏名をｂ[ｉ]に入れておきます。学籍番号ｘを与えて、配列ａから一致した要素のｉを知ることにより、その学生氏名ｂ[ｉ]を得るというような操作は、事務処理のプログラムでよく用いられる操作です。技術計算の分野では、数表を検索することはよく用いられる操作です。
ここでは、ポピュラーなサーチのアルゴリズムであるリニアサーチ（順次探索法）、バイナリサーチ（二分探索法）について説明します。
リニアサーチ（順次探索法）
リニアサーチとは、右図のように、ａ[1]から順にａ[2]、ａ[3]、・・・と探していく方法です。この場合には、配列ａの要素はソートされている（小さい順に並べられている）必要はありません。
このときの流れ図は、下左図になります。
よく検索される要素を先頭に配置しておけば、検索での比較回数が少なくなります。
しかし、一致する要素が存在しない場合には、最後まで探索しなければならず比較回数が大きくなります。
それに対して、配列が事前に昇順にソートしてあれば、ｘ＞ａ[ｉ]になったときに、存在しないことがわかります。ソートされているときの流れ図を下右図に示します。
どちらの場合も、サーチする値ｘの出現にばらつきがないならば、ｘとａ[ｉ]の平均比較回数は（ソートされていない場合での非存在のケースを無視すれば）、ｎ／２回になります。
配列を事前にソートしておくかどうかは、探索する値の特徴によります。
探索の値の大部分が少数の場合は、それを配列の先頭に配置すれば、比較回数が小さくなるので、事前ソートしないほうが高速になります。
非存在（配列に存在しない）の探索が多い場合、事前にソートされていないと、配列の最後まで探索しないと非存在であることがわかりません。
バイナリサーチ（二分探索法）
バイナリサーチは、配列ａが事前にソートされている場合に、比較回数を少なくできるアルゴリズムです。
右図のように、比較のたびに、探索領域を半分にしていくのが特徴です。その流れ図を示します。
- amin＝１、amax＝ｎとします。amin～amaxが探索範囲です。
- 通常は amin≦amax のはずです。そうでなくなったときには、一致する要素が存在しなかったことになります（その説明は省略）。
- aminとamaxの中点ｉ＝(amin＋amax)／２を計算して、ｘとａ[ｉ]を比較します（右図のアの要素になります）。
一致したならば、このｉが求めるものですから、処理を終わります。
- ｘ＜ａ[ｉ] ならば、一致する要素はｉよりも小さい（上にある）のですから、amax＝i-1 として、２に戻ります（右図では、２回目にイの要素になります）。
ｘ＞ａ[ｉ] ならば、一致する要素はｉよりも大きい（下にある）のですから、amin＝i+1 として、２に戻ります（右図では、３回目にウの要素になります）。
右図でのア→イ→ウ→・・・のように探索範囲を半分にしながら探索していく間に、３でｘ＝[ｉ] となるか、２で amin＞amax となり、処理が終わります。
１回の比較で、探索範囲が半分になるということは、探索を１回増やせば、探索範囲を２倍にすることができるということです。探索回数をｍとすれば、２m＝ｎ、すなわち、ｍ＝log2ｎの関係があります。
バイナリサーチは、リニアサーチと比較して、一般的に高速ですが、リニアサーチのほうが高速な場合があります。
- 探索配列が極端に小さい場合
バイナリサーチは比較回数は小さいのですが、処理が複雑で、しかも計算時間のかかる割り算があります。そのため、極端に少ない配列を探索する場合はリニアサーチのほうが高速なことがあります。 - 探索値に大きなばらつきがある場合
配列が大きいのに、探索される値が非常に偏っているとき、探索頻度の多いものを配列の先頭に配置しておけば、比較回数が小さくなります。
バイナリサーチのトレース
配列ａには、ｎ＝８個の要素が、次のように入っているとします。
ｉ １ ２ ３ ４ ５ ６ ７ ８
ａ[ｉ] １０ ２０ ３０ ４０ ５０ ６０ ７０ ８０
ｘ＝５０ のとき
初期値：amin＝１、amax＝８
１回目：ｉ＝(amin＋amax)／２＝(１＋８）／２＝４.５→小数点以下切り捨てで、ｉ＝４
ａ[４]＝４０＜ｘ なので、amin＝ｉ＋１＝５
２回目：ｉ＝(５＋８）／２＝６.５→ｉ＝６
ａ[６]＝６０＞ｘ → amax＝ｉ－１＝５
３回目：ｉ＝(５＋５）／２＝５
ａ[５]＝５０＝ｘ → 一致した
ｘ＝３５ のとき
初期値：amin＝１、amax＝８
１回目：ｉ＝(１＋８）／２＝４.５→ｉ＝４
ａ[４]＝４０＞ｘ なので、amax＝ｉ－１＝３
２回目：ｉ＝(１＋３）／２＝２
ａ[２]＝２０＜ｘ → amin＝ｉ＋１＝３
３回目：ｉ＝(３＋３）／２＝３
ａ[３]＝３０＜ｘ → amin＝ｉ＋１＝４
amin＝４＞amax＝３ となり「存在せず」になります。
先に示した文章によるアルゴリズムの説明は不十分です。どうしてどうして２で amin≦amax の条件にするのか、どうして４では amax＝i-1 でなければならず、amax＝i ではだめなのかなどが疑問になります。
●amin＜amax としたとき（ｘ＝１０ の指定で「存在せず」になってしまう）
初期値：amin＝１、amax＝８
１回目：ｉ＝(１＋８）／２＝４.５→ｉ＝４
ａ[４]＝４０＞ｘ なので、amax＝ｉ－１＝３
２回目：ｉ＝(１＋３）／２＝２
ａ[２]＝２０＞ｘ → amax＝ｉ－１＝１
ここで、amin(＝１)＝amax(＝１) となり打ち切られ、「存在せず」になってしまいます。
●amin=i, amax=i としたとき（ｘ＝３５ の指定で「無限ループ」になってしまう）
初期値：amin＝１、amax＝８
１回目：ｉ＝(１＋８）／２＝４.５→ｉ＝４
ａ[４]＝４０＞ｘ なので、amax＝ｉ＝４
２回目：ｉ＝(１＋４）／２＝２.５→ｉ＝２
ａ[２]＝２０＜ｘ →amin＝ｉ＝２
３回目：ｉ＝(２＋４）／２＝３
ａ[３]＝３０＜ｘ → amin＝ｉ＝３
４回目：ｉ＝(３＋４）／２＝３.５→ｉ＝３
ａ[３]＝３０＜ｘ → amin＝ｉ＝３
５回目：ｉ＝(３＋４）／２＝３.５→ｉ＝３
ａ[３]＝３０＜ｘ → amin＝ｉ＝３
：
となり、これが無限に繰り返されます。
ハッシュサーチ
ハッシュサーチとは、直接編成ファイル（ハッシュファイル）から、与えたキー項目の値をもつレコードを検索することです。
ハッシュファイルでは、キー項目の値をハッシュ関数により変換したハッシュ値をアドレスにして格納されています。ですから、ハッシュ関数により与えたキー項目の値を計算したハッシュ値を用いて１回の検索ですみます。計算量オーダーは Ｏ(１) になります。
バイナリサーチの計算プログラム
正しいアルゴリズム（パターン０）と、あえて誤りのアルゴリズム（パターン１、２）によるプログラムを掲げます。経過が表示されますので、いろいろなケースを与えて、実験してください。