2 リニアサーチ

リニアサーチ(linear search)は，逐次検索あるは順検索(sequential search)とも呼ばれ， 配列などに格納されたデータを一つ一つ順に端から調べるだけの，素朴な方法である．

2.1 単純な方法

2.1.1 原理

原理は簡単で，配列の端から比較を行い，目的の整数を捜しているだけである．もう少し 詳しい説明は，教科書に書かれている．もし，配列が整理されておらずランダムに並んで いる場合，この方法しか無い．

このリニアサーチの計算量のオーダーを考えよう．単純なリニアサーチのプログラムは， 教科書のList 2-1(p.37)に示されているとおりで，同じものをプリントのリスト 1に載せてある．このプログラムで，もっとも多く実行される，すなわ ちもっとも多くの時間がかかる命令は，リスト1の13行目

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

である．もし，$n$ 個のデータがあり，その中に目的のデータ(キー)がある場合，この命 令の平均実行回数は$n/2$ である．データの中にキーが無い場合，$n$ 回，その命令は実行 される．データの中にキーの有無で平均実行回数は変わるが，いずれにしても計算量のオー ダーは$O(n)$ である．

2.1.2 フローチャート

教科書のList 2-1(p.37)あるいはこのプリントのリスト1のプログラム のフローチャートを図1に示す．

図 1: 単純なリニアサーチのフローチャート．

2.1.3 プログラム

単純なリニアサーチのプログラムをリスト1に示す．これは，教科 書のList 2-1(p.37-38)と同じである(転載について)．

リスト1 リニアサーチ

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <time.h>
   4 
   5 #define NOT_FOUND   (-1)
   6 #define N           (10)
   7 
   8 int linear_search(int x,int *a,int num)
   9 {
  10     int n=0;
  11 
  12     /* 配列の範囲内で目的の値を探す */
  13     while(n<num&&a[n]!=x)
  14         n++;
  15 
  16     if(n<num)
  17         return n;
  18 
  19     return NOT_FOUND;
  20 }
  21 
  22 int main(void)
  23 {
  24     int i,r,array[N];
  25 
  26     srand((unsigned int)time(NULL));
  27 
  28     /* 適当な配列を作る */
  29     printf("array ");
  30     for(i=0;i<N;i++)
  31         printf("[%d]:%d ",i,array[i]=rand()%20);
  32 
  33     printf("\n何を探しますか:");
  34     scanf("%d",&i);
  35 
  36     r=linear_search(i,array,N);
  37 
  38     if(r==NOT_FOUND)
  39         printf("%dは見つかりません\n",i);
  40     else
  41         printf("%dは%d番目です\n",i,r);
  42 
  43     return EXIT_SUCCESS;
  44 }

2.2 番兵を使う方法

2.2.1 原理

最初に示したリスト1のプログラムは，ちょっとした工夫で実行速度を 向上させることができる．リスト1のもっとも計算時間がかかる13行目 は，2つの比較(n<numとa[n]!=x)を行っている．キーを配列の最後に入れる(番 兵)ことにより，n<numの比較の計算を行わないで済むようにできる．こうすると配 列の最後では，a[n]!=x]が成立しなくなるので，ループから抜けることになる．ルー プから抜けた後，キーと元々あった配列の最後の値と比較すればよいのである．

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

2.2.2 フローチャート

番兵を使うリニアサーチのプログラムである教科書のList 2-2(p.38-39)あるいはこのプ リントのリスト2のプログラムのフローチャートを図2 に示す．番兵をどのように処理しているか，理解せよ．

図 2: 番兵を使うリニアサーチのフローチャート．

2.2.3 プログラム

番兵を使うリニアサーチのプログラムをリスト2に示す．こ れは，教科書のList 2-2(p.38-39)と同じである(転載について)．

リスト2 番兵を使ったリニアサーチ

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <time.h>
   4 
   5 #define NOT_FOUND   (-1)
   6 #define N           (10)
   7 
   8 int search(int x,int *a,int num)
   9 {
  10     int     n=0,t;
  11 
  12     /* 最後の値をxに入れ替える（番兵） */
  13     t=a[num-1];
  14     a[num-1]=x;
  15 
  16     /*目的の値を探す*/
  17     while(a[n]!=x)
  18         n++;
  19 
  20     a[num-1]=t;     /* 配列最後の値を元に戻す */
  21     if(n<num-1)
  22         return n;   /* いちばん最後以外で一致 */
  23     if(x==t)
  24         return n;   /* いちばん最後が一致 */
  25 
  26     return NOT_FOUND;
  27 }
  28 
  29 int main(void)
  30 {
  31     int     i,r,array[N];
  32 
  33     srand((unsigned int)time(NULL));
  34 
  35     /* 適当な配列を作る */
  36     printf("array ");
  37     for(i=0;i<N;i++)
  38         printf("[%d]:%d ",i,array[i]=rand()%20);
  39 
  40     printf("\n何を探しますか:");
  41     scanf("%d",&i);
  42 
  43     r=search(i,array,N);
  44     if(r==NOT_FOUND)
  45         printf("%dは見つかりません\n",i);
  46     else
  47         printf("%dは%d番目です\n",i,r);
  48 
  49     return EXIT_SUCCESS;
  50 }

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

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

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

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