二分で書けない二分探索
C言語で二分探索をつくってみました
#include<stdio.h> #include<time.h> #include<stdlib.h> #define MAX 100 int binaly_search(int array[],int first,int last,int n) { int mid = (first+last)/2; if(first+1 == last){ if(array[last] == n) return last; else return -1; } else if(array[mid] >= n) return binaly_search(array,first,mid,n); else return binaly_search(array,mid,last,n); } int linear_search(int array[],int n,int size) { int i; for(i=0;i<size;i++) if(array[i]==n) return i; return -1; } void quicksort(int array[],int first,int last) { int i=first,j=last,std = array[(first+last)/2],tmp; while(1){ while(array[i] < std) i++; while(array[j] > std) j--; if(i >= j) break; tmp = array[j]; array[j] = array[i]; array[i] = tmp; i++; j--; } i--; j++; if(i-first > 0) quicksort(array,first,i); if(last-j > 0) quicksort(array,j,last); } int main() { int target,i,array[MAX]; srand((unsigned)time(NULL)); for(i=0;i<MAX;i++) array[i] = rand() % MAX; //整列 quicksort(array,0,MAX-1); for(i=0;i<MAX;i++) printf("array[%d] = %d\n",i,array[i]); printf("\n"); target = rand() % MAX; //線形探索 printf("Search : %d by linear search.\n",target); if((i = linear_search(array,target,sizeof(array)/sizeof(int))) == -1) printf("%d is not found.\n",target); else printf("%d is in array[%d].\n",target,i); //二分探索 printf("Search : %d by binaly search.\n",target); if((i = binaly_search(array,0,MAX-1,target)) == -1) printf("%d is not found.\n",target); else printf("%d is in array[%d].\n",target,i); return 0; }
二分探索部分は再帰を用い、範囲をせばめてfirst部とlast部が隣接したときに
last部を比較し、nと一致したらlastを返すようにしました。
配列ではじめにnが現れる場所を探し、
一致するものがないとき、-1を返します。
乱数配列を適当につくってクイックソートで整列し、探索対象も乱数で指定してサーチするようにしています。
二分探索の結果を確認するために、リニアサーチも実装しました。
これを実行すると、
$ ./binaly array[0] = 1 array[1] = 1 array[2] = 2 array[3] = 3 ... array[83] = 84 array[84] = 85 array[85] = 86 ... array[99] = 98 Search : 85 by linear search. 85 is in array[84]. Search : 85 by binaly search. 85 is in array[84].
こんな感じになります
しかし、探索対象が0のとき
$ ./binaly array[0] = 0 array[1] = 1 array[2] = 4 array[3] = 6 ... array[98] = 96 array[99] = 98 Search : 0 by linear search. 0 is in array[0]. Search : 0 by binaly search. 0 is not found.
二分探索側で0が発見できません...ｺﾏﾘﾏｼﾀﾈｴ
二分探索のコードを見直すと、
int binaly_search(int array[],int first,int last,int n) { int mid = (first+last)/2; if(first+1 == last){ if(array[last] == n) return last; else return -1; } else if(array[mid] >= n) return binaly_search(array,first,mid,n); else return binaly_search(array,mid,last,n); } int linear_search(int array[],int n,int size) { int i; for(i=0;i<size;i++) if(array[i]==n) return i; return -1; }
そもそものアルゴリズムを見直してみると、
[1]mid = (first+last)/2 とする(小数点切り捨て)。
[2]first+1==last のとき、array[last]がnと等しければlastを返し、等しくなければ-1を返す。そうでなければ、array[mid]が目的値 nより小さいとき firstをmidとして[1]へ、それ以外のときlastをmidとして[1]へ
この条件を繰り返し、first+1==lastとなるとき、lastはarray[last] >= nを満たしています。firstはその逆のarray[first] < nを満たしています。firstとlastはもとはmidだった数なので、array[mid]として比較されているからです。このとき、配列はソートされていて単調なため、array中にnが存在するならば、array[last]はnを指しているはずです。言い換えると、firstは条件(array[a] < n)を満たす最大のa、lastは条件(array[a] >= n)を満たす最小のaとなります。
例えば、不等号を少しいじって else if(array[mid] > n)とすると、lastは条件(array[a] > n)を満たす最大のaを指すようになり、firstは(array[a] <= n)を満たす最大のaを指すようになります。このとき、nが存在するならばarray[first]はnを指しています。nが複数あるときは、その最後尾のnを指しています。
しかし、array[first] <= array[last]かつfirst < lastなので
array中に0が一つしかないとき、array[last]には配列で最も小さい数が入ることはありません
条件を逆にしたときも同様の問題で、そのときは配列で最も大きい数値を探すことができません。
これを解決するために、array[first]とnを比較してから、array[last]と比較するようにしました。
int binaly_search(int array[],int first,int last,int n) { int mid = (first+last)/2; if(first+1 == last){ if(array[first] == n) return first; if(array[last] == n) return last; else return -1; } else if(array[mid] >= n) return binaly_search(array,first,mid,n); else return binaly_search(array,mid,last,n); }
target = array[0]として実行結果
$ ./binaly array[0] = 0 array[1] = 0 ... array[98] = 96 array[99] = 99 Search : 0 by linear search. 0 is in array[0]. Search : 0 by binaly search. 0 is in array[0].
array[last]と比較してからarray[first]と比較するようにすると、上の実行例のように0が2つ連続しているときに、last==1なので、array[last]==nを満たし、1が出力されてしまいます。値がnである配列の一番小さい添字を印字するようにしたかったので、この順番になりました。ほとんどの場合、firstは出力されないから無駄な処理になってしまうのがなんとも...
なんかもっといい方法はないですかね
