二分探索法(バイナリサーチ)

http://www.geocities.jp/ky_webid/algorithm/007.html

二分探索法は、あらかじめ配列を昇順あるいは降順にソートしておくことが前提になります。そして、まず配列の中央にある要素を調べます。もし目的の値と異なっていれば、目的の値とその位置にある値との大小関係を元に、配列の前半あるいは後半だけを調べるように、次の探索対象の範囲を設定します。

ソートとの合わせ技ですね。さっそく試してみます。因みにソートはシェルソートを用います。

#include <stdio.h>
#define ARRAY_NUM(a) (sizeof(a)/sizeof(a[0]))

int binary_search (int *,int,int);
void swap (int *, int *);
void shell_sort (int *, int );

void swap (int *a, int *b) {
    int work = *a;
    *a = *b;
    *b = work;
}

void shell_sort (int *data, int array_size) {
    int h;
    int i,j;
    
    if ( array_size <= 1 ) {
        return;
    }
    
    for(h=1; h<array_size; h=h*3+1);
    
    for(h/=3;h>0;h/=3){
        for(i=h; i<array_size; ++i){
            for(j = i;j >= h && data[j-h] > data[j];j -= h){
                swap(&data[j],&data[j-h]);
            }
        }
    }
}

int binary_search (int *data,int array_size,int target) {
    int i = array_size / 2;
    
    while(data[i] != target){
        if ( 0 == i ) return 0;
        if ( array_size - 1 <= i ) return 0;
        if ( data[i] > target ) {
            array_size = i + 1;
            i -= array_size / 2;
        }
        else {
            i += (array_size - i) / 2;
        }
    }
    
    return 1;
}

int main (void) {
    int num[] = { 3,9,11,50,7,34,20,98,6,1 };
    int i;
    
    shell_sort(num,ARRAY_NUM(num));
    
    for(i=0;i<=100;i++) {
        printf("%d %d\n",i,binary_search(num,ARRAY_NUM(num),i));
    }
    
    return 0;
}

できました。なるべくforを使おうと思ったのですが、やっぱやりにくかったのでwhileにしてしまいました。

割とシンプルにかけたと思います。まぁ多分解答例はもっとシンプルだとは思いますがw

初めは範囲を保存しておくための変数を用意してたんですが、iだけでなんとかなりそうかなと思い色々試していたら今の形になりました。

一応自作リニアサーチとのベンチマークも取ってみました。

#include <stdio.h>
#include <time.h>
#define ARRAY_NUM(a) (sizeof(a)/sizeof(a[0]))

double benchmark(int,void (*)(void));
int binary_search (int *,int,int);
int linear_search (int *,int,int);
void swap (int *, int *);
void shell_sort (int *, int );

void swap (int *a, int *b) {
    int work = *a;
    *a = *b;
    *b = work;
}

void shell_sort (int *data, int array_size) {
    int h;
    int i,j;
    
    if ( array_size <= 1 ) {
        return;
    }
    
    for(h=1; h<array_size; h=h*3+1);
    
    for(h/=3;h>0;h/=3){
        for(i=h; i<array_size; ++i){
            for(j = i;j >= h && data[j-h] > data[j];j -= h){
                swap(&data[j],&data[j-h]);
            }
        }
    }
}

int binary_search (int *data,int array_size,int target) {
    int i = array_size / 2;
    
    while(data[i] != target){
        if ( 0 == i ) return 0;
        if ( array_size - 1 <= i ) return 0;
        if ( data[i] > target ) {
            array_size = i + 1;
            i -= array_size / 2;
        }
        else {
            i += (array_size - i) / 2;
        }
    }
    
    return 1;
}

int linear_search (int *data,int array_size,int target) {
    int i;
    
    for(i=0;i<array_size;i++) {
        if ( data[i] == target ) {
            return 1;
        }
    }
    
    return 0;
}

void linear (void) {
    int num[] = { 3,9,11,50,7,34,20,98,6,1,100,30,21,22,23,24,25,26,27,28,29,31,32,33,35,36,37,38,39 };
    int i;
    for(i=0;i<=10000;i++) {
        linear_search(num,ARRAY_NUM(num),i);
    }
}

void binary (void) {
    int num[] = { 3,9,11,50,7,34,20,98,6,1,100,30,21,22,23,24,25,26,27,28,29,31,32,33,35,36,37,38,39 };
    int i;
    shell_sort(num,ARRAY_NUM(num));
    for(i=0;i<=10000;i++) {
        binary_search(num,ARRAY_NUM(num),i);
    }
}

int main (void) {
    int count = 1000;
    
    printf("linear %f sec\n",benchmark(count,linear));
    printf("binary %f sec\n",benchmark(count,binary));
    return 0;
}

double benchmark(int count,void (*func)(void)){
    clock_t start,end;
    int i;
    start = clock();
    
    for(i=0;i<count;++i){
        (*func)();
    }
    
    end = clock();
    return (end - start) / (double)CLOCKS_PER_SEC;
}
$ bench
linear 1.578000 sec
binary 0.578000 sec

イナリサーチの方が早くなりました。ちょっと一安心です。

解答例との比較

解答例では上限と下限を管理する変数を用意してやっていますね。迷ったんですけどね・・・。

でも明らかに解答例の方が読みやすいですね。

また、ベンチマークも取ってみるために

int binary2_search (int *data,int array_size,int target) {
    int low = 0;
    int high = array_size - 1;
    int mid;
    
    while( low <= high ) {
        mid = (low + high) / 2;
        if( data[mid] == target ) {
            return 1;
        }
        else if( data[mid] < target ) {
            low = mid + 1;
        }
        else {
            high = mid - 1;
        }
    }
    
    return 0;
}

このように関数に切り出して確認したところ

linear  1.578000 sec
binary  0.593000 sec
binary2 0.750000 sec

おお、自分で作ったバイナリサーチの方が僅かながらに早い!ちょっと嬉しいですね。

・・・ただし・・・。自作のバイナリサーチはテストが疎かなので間違っている可能性が無きにしも非ずなんですよねぇ・・・。

今後の予定としてコードの断片のテストのやり方とかを調べられればいいなと思っています。