3 サーチのアルゴリズム

サーチとは，

文字どおりたくさんのデータの中から目的のデータ(キー)がどこにあるか(もしくは，あるかな いか)を調べる作業

である．整数のデータが配列に格納されている場合について，目的のデータを探す方法を 学習した．

3.1 リニアサーチ

3.1.1 原理

目的のデータを端から順に探索する方法である．データがランダムに並んでいる場合，こ の方法しかない．

このアルゴリズムの計算のオーダーは，$O(N)$ である．なぜならば，端から探索していく ため，データが一致するためには平均$N/2$ 回の比較が必要であるからである⁴．

3.1.2 プログラム

教科書のList 2-1(p.37-38)のリニアサーチの関数は，リスト 7の通りである．これをmain関数から呼び出すことにより， 整数xと一致する配列aの添え字の番号が求められる．

• xが探索するデータである．
• 配列はポインターとして渡されている．main関数の実引数の配列名は，ポイ ンターである．この関数では，main関数の呼び出し側の配列は，a[] という配列になる．
• numがデータ数を表す．
• 目的のデータと一致するものが無かった場合，NOT_DOUNDを返す．この値は， #defineで置換されれる．

リスト7 リニアサーチ の関数(転載について)

   1 int linear_search(int x,int *a,int num)
   2 {
   3     int n=0;
   4 
   5     /* 配列の範囲内で目的の値を探す */
   6     while(n<num&&a[n]!=x)
   7         n++;
   8 
   9     if(n<num)
  10         return n;
  11 
  12     return NOT_FOUND;
  13 }

3.2 番兵をつかったリニアサーチ

3.2.1 原理

リスト7の計算速度を上げるために，通常のリニアサーチでは番兵を つかう．リスト7では，1回のループで，

	n<num&&a[n]!=x

のように2回の比較(n<numとa[n]!=x)を行っている．目的のデータ(キー)を配 列の最後に入れる(番兵)ことにより，n<numの比較の計算を行わないで済むようにで きる．こうすると配列の最後では，a[n]!=x]が成立しなくなるので，ループから抜 けることになる．ループから抜けた後，キーと元々あった配列の最後の値と比較すればよ いのである．

このようにすると，比較の数が半分になる．しかし，計算量のオーダーは$O(N)$ と変わら ないことに注意しよう．

3.2.2 プログラム

教科書のList 2-2(p.38-39)の番兵を用いたリニアサーチの関数は，リスト 8の通りである．引数は，先ほどの番兵を用いないリ ニアサーチと同じ．

リスト8 番兵を使った リニアサーチの関数(転載について)

   1 int search(int x,int *a,int num)
   2 {
   3     int     n=0,t;
   4 
   5     /* 最後の値をxに入れ替える（番兵） */
   6     t=a[num-1];
   7     a[num-1]=x;
   8 
   9     /*目的の値を探す*/
  10     while(a[n]!=x)
  11         n++;
  12 
  13     a[num-1]=t;     /* 配列最後の値を元に戻す */
  14     if(n<num-1)
  15         return n;   /* いちばん最後以外で一致 */
  16     if(x==t)
  17         return n;   /* いちばん最後が一致 */
  18 
  19     return NOT_FOUND;
  20 }

3.3 バイナリーサーチ

3.3.1 原理

データの並びに規則性が無い場合，リニアサーチのように端から順に捜すしかない．しか し，データの並びに規則性がある場合，その性質を利用できる．

たとえば，データが昇順に並んでいた場合，端から比較するのではなく，最初に真ん中に位置す るデータと比較する．すると，サーチすべきデータの個数が1回の比較でに半分になる．同じこ とを繰り返すと，比較すべき対象が$1/2$ ずつ減少する．データの個数が多い場合，この 方法は劇的にサーチが早くなる．この方法をバイナリーサーチと言う．

リニアサーチだと，1回の比較で1個しかデータの候補が減らないのに，バイナリーサーチ だと半分に減少させることができるのである．ただし，バイナリーサーチを使うために は，データを予めソートしておく必要がある．サーチの回数が1回であれば，ソートの手 間を考えるとリニアサーチの方が良い．サーチの回数が増加すると，バイナリーサーチの 方が有利になる．

1回の計算，リスト9の5〜15行のループで，検索する範囲は$1/2$ にな る．したがって，$\alpha$ 回のループでその範囲が1になれば計算が終了する．データの 個数を$N$ として，式で表すと，

$$N\left(\frac{1}{2}\right)^{\alpha}=1$$ (2)

となる．これから，計算回数$\alpha$ は，

$$\alpha=\log_2 N$$ (3)

と導き出せる⁵．バイナリーサーチの場合の計算量のオーダーは， $O(\log_2 N)$ である．

3.3.2 プログラム

教科書のList 2-3(p.41-42)のバイナリーサーチの関数は，リスト 9の通りである．これをmain関数から呼び出すことにより， 整数xと一致する配列aの添え字の番号が求められる．

• 配列はポインターとして渡されている．main関数の実引数の配列名は，ポイ ンターである．
• leftがデータが存在する左端で，rightが右端を表す．
• 目的のデータと一致するものが無かった場合，NOT_DOUNDを返す．この値は， #defineで置換されれる．

リスト9 バイナリーサー チの関数(転載について)

   1 int binary_search(int x,int *a,int left,int right)
   2 {
   3     int     mid;
   4 
   5     while(left<=right)
   6     {
   7         mid=(left+right)/2;
   8         if(a[mid]==x)
   9             return mid;
  10 
  11         if(a[mid]<x)
  12             left=mid+1;     /* midより左側にxは存在しない */
  13         else
  14             right=mid-1;    /* midより右側にxは存在しない */
  15     }
  16 
  17     /* サーチ範囲がなくなっても一致するものはなかった */
  18     return NOT_FOUND;
  19 }

[転載について]
このペー ジ中のリスト7とリスト8，リスト9のプロ グラムは，教科書として使用している以下の書籍

書名	プログラミングの宝箱　アルゴリズムとデータ構造 ISBN4-7973-2419-8
著作者	紀平拓男・春日伸弥
出版社	ソフトバンク　パブリッシング株式会社

から転載しました．この転載に関しては，著者と版元に許諾を得ています．

ホームページ: Yamamoto's laboratory
著者: 山本昌志