２分探索で値を検索

2013年3月29日：アルゴリズム

降順あるいは昇順で並べられたデータ配列から特定の値を探す方法に２分探索があります。

もちろん、はじめから順に探索する線形探索でもいいのですが、順に並べられているデータなら２分探索の方が速く検索できます。

ここでは、２分探索について解説していきます。

２分探索とは

２分探索は、名前の通りデータを２つに分けながら探索します。

例えば、

1,3,5,7,12,26,55,78

から56があるか調べる場合は、中間の12に着目します。

1,3,5,7,12,26,55,78

そして、56は12より大きいので12より右のデータにあることになります。

1,3,5,7,12,26,55,78

同様に、26,55,78の中間の55に着目します。

26,55,78

56は55より大きいので、右側に56はあることがわかります。

26,55,78

残るは78だけなので、56は存在しないことがわかります。

２分探索をコーディングする

ではプログラムで組んでいきます。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int nibun(int a[], int n, int target){
    int hajime=0;    //開始位置
    int owari=n-1;    //最終位置
    while(true){
        int center=(hajime+owari)/2;    //中間位置を取得
        if(a[center]==target){            //もし中間が目的値なら
            return center;                //中間位置を返す
        }else if(a[center]<target){        //もし目的値が上なら
            hajime=center+1;            //はじめを中心+1とする
        }else{
            owari=center-1;                //それ以外は最終位置を中心-1にする
        }
        if(owari==hajime){    //もし終わったら
            break;            //ループを抜ける
        }
    }
    return -1;
}

二分探索の計算量

では二分探索の計算量を計算します。

まず、線形探索の場合は、nこのデータに関して一つづつ調べるのでオーダーはnとなります。

一方、二分探索の場合は

  • 一回目のデータの長さ：n
  • 二回目のデータの長さ：n/2
  • 三回目のデータの長さ：n/4
  • …
  • 最終のデータの長さ：1

なので、t回実行して最終まで来たとするとざっくり

　n/2^{t}\approx1

が成り立ちます。よって、

　t\approx \log_{2}n

が得られます。オーダーは\log_{2}nだとわかります。線形探索のnよりオーダーが小さくなりますね。

著者：安井 真人(やすい　まさと)

TOP