[Previous: 2 リニアサーチ] [Up: サーチ] [Next: 4 課題]
Subsections

3 バイナリーサーチ

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

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

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

3.1 通常の方法

3.1.1 原理

原理は単純で，データが昇順に並んでいる場合を考えれば理解できる．キーのある範囲を $ [left,right]$ とする．これは，配列a[left]とa[right]の間が候補で， この中にキーがある可能性があるということである．この範囲外には，キーと一致するデー タは絶対に無いのである．データが$ n$ 個ある場合，a[0]からa[n-1] の範囲が候補なので，$ [0,n-1]$ の間にあると表現するのである．

つぎに， $ mid=(left+right)/2$ とキーxを比較する．この比較の結果，

が言える．これを繰り返すことにより，キーと一致するデータのある場所を捜す．

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

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

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

$\displaystyle \alpha=\log_2 n$ (2)

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

3.1.2 フローチャート

単純なバイナリーサーチのプログラムである教科書のList 2-3(p.41-42)あるいはこのプ リントのリスト3のプログラムのフローチャートを図3 に示す．
図 3: 単純なバイナリーサーチ．
\includegraphics[keepaspectratio,scale=1.0]{figure/flow_3.eps}

3.1.3 プログラム

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

リスト3 バイナリーサーチ(転載について)

   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 binary_search(int x,int *a,int left,int right)
   9 {
  10     int     mid;
  11 
  12     while(left<=right)
  13     {
  14         mid=(left+right)/2;
  15         if(a[mid]==x)
  16             return mid;
  17 
  18         if(a[mid]<x)
  19             left=mid+1;     /* midより左側にxは存在しない */
  20         else
  21             right=mid-1;    /* midより右側にxは存在しない */
  22     }
  23 
  24     /* サーチ範囲がなくなっても一致するものはなかった */
  25     return NOT_FOUND;
  26 }
  27 
  28 int main(void)
  29 {
  30     int     i,r,array[N];
  31 
  32     srand((unsigned int)time(NULL));
  33 
  34     /* 適当なソートされた配列を作る */
  35     printf("array ");
  36     printf("[0]:%d ",array[0]=rand()%3);
  37     for(i=1;i<N;i++)
  38         printf("[%d]:%d ",i,array[i]=array[i-1]+rand()%3);
  39 
  40     printf("\n何を探しますか:");
  41     scanf("%d",&i);
  42 
  43     r=binary_search(i,array,0,N-1);
  44 
  45     if(r==NOT_FOUND)
  46         printf("%dは見つかりません\n",i);
  47     else
  48         printf("%dは%d番目です\n",i,r);
  49 
  50     return EXIT_SUCCESS;
  51 }

3.2 先頭を返す方法

3.2.1 原理

キーと一致するデータが複数ある場合，ソートされているので，それらは配列で同じ値が 続くことになる．この場合，リスト3だとそれらのうち最初に一致した 位置を返すことになる．どれに一致するかは，データに依存する．このように複数と一致 する場合は，その先頭の位置を知りたいことがある．

このように，先頭を知りたい場合は必ずとなり通しと比較するようにすればよい．そのよ うにするためには，3を改良して，4のようにすれば良 い．

3.2.2 フローチャート

同じ値が続く場合にその先頭の位置を返すバイナリーサーチのプログラムである教科書の List 2-4(p.44-45)あるいはこのプリントのリスト4のフローチャートを 図4 に示す．
図 4: 一致する配列の先頭を返すバイナリーサーチのフローチャート．
\includegraphics[keepaspectratio,scale=1.0]{figure/flow_4.eps}

3.2.3 プログラム

一致するデータが複数の場合，もっとも先頭に近い位置を返すバイナリーサーチのプログラムをリスト4に示す．これは，教科 書のList 2-4(p.44-45)と同じである(転載について)．

リスト4 先頭を返すバイナ リーサーチ(転載について)

   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 binary_search(int x,int *a,int left,int right)
   9 {
  10     int      mid;
  11 
  12     while(left<right)
  13     {
  14         mid=(left+right)/2;
  15         if(a[mid]<x)
  16             left=mid+1;
  17         else
  18             right=mid;
  19     }
  20     if(a[left]==x)
  21         return left;
  22 
  23     /* サーチ範囲がなくなっても一致するものはなかった */
  24     return NOT_FOUND;
  25 }
  26 
  27 int main(void)
  28 {
  29     int     i,r,array[N];
  30 
  31     srand((unsigned int)time(NULL));
  32 
  33     /* 適当なソートされた配列を作る */
  34     printf("array ");
  35     printf("[0]:%d ",array[0]=rand()%3);
  36     for(i=1;i<N;i++)
  37         printf("[%d]:%d ",i,array[i]=array[i-1]+rand()%3);
  38 
  39     printf("\n何を探しますか:");
  40     scanf("%d",&i);
  41 
  42     r=binary_search(i,array,0,N-1);
  43 
  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 }

[転載について]
このページ中のリスト3とリスト4のプロ グラムは，教科書として使用している以下の書籍
書名プログラミングの宝箱　アルゴリズムとデータ構造 ISBN4-7973-2419-8
著作者紀平拓男・春日伸弥
出版社ソフトバンク　パブリッシング株式会社
から転載しました．この転載に関しては，著者と版元に許諾を得ています．



[Previous: 2 リニアサーチ] [Up: サーチ] [Next: 4 課題]
[Top:ページの先頭に戻る]

ホームページ: Yamamoto's laboratory
著者: 山本昌志
Yamamoto Masashi
2005-11-21

no counter