2分探索アルゴリズムの考え方とc++のソース

2分探索アルゴリズムとは

2分探索(binary search)アルゴリズムは、まず昇順or降順にソートした後に、探索開始位置を2分しながら
数値の大小をチェックし探索していくアルゴリズムになります。

では、2分探索のアルゴリズムの使用例を見ていきます。

2分探索アリゴリズムの使用例

以下のような要素を10個持つ数列があるとします。

10 8 12 6 14 4 16 2 18 20

この数列を2分探索を行うために、昇順または降順にソートします。
今回は、昇順にソートします。

2 4 6 8 10 12 14 16 18 20

では、この数列から4が存在するかどうかを
2分探索アルゴリズムを使い、探索してみます。

2分探索では探索位置を記憶するための変数として、
左辺値(left)・中央値(center)・右辺値(right)
を使います。
役割をそれぞれ説明すると、

左辺値(left)=先頭要素の位置

中央値(center)=左辺値と右辺値を足して2で割った中間の要素の位置

右辺値(right)=末尾の要素の位置

をそれぞれ示しています。

では、2分探索を実行してみます。

2分探索を実行する

1.中央位置を決定する

数列を配列だとみなすと、
leftが0、rightが9なので、centerが(0 + 9) / 2 = 4(小数点を切り捨てた)になるので、
探索位置はのindexは4です。

数列の要素4に該当するのは、

10です。

2.中央値とkeyとなる数値の大小をチェックする

探索値10とkey4の大小を調べます。

4 < 10なので、rightの9をcenterの4にし、
centerの値を再度計算します。

center = (0 + 4) / 2 = 2

後は、このように
1.2の計算を繰り返すことにより、
半分づつ探索位置をずらしながら、
探索を実行していきます。

では、2分探索のルールに従い探索を続けていきます。

center2の数値は6
一致しないので、
再度計算します。

rightに中央の位置を代入して、

right = 2

中央の位置を計算して、

center = (0 + 2) / 2 = 1

centerのindex1の数値は4となり一致したので、
2分探索終了です。

探索回数は3回でした。

探索値が大きかった場合

探索値が大きかった場合はleftを変更しますが、

leftの位置をずらす場合は、
left = center + 1
とします。

これは、keyとなる数値が探索数列内の値を超えていた場合 ループしてしまうからです。

2分探索の実行回数

2分しながら探索していていくことから、
探索回数はO(logn)になります。

c++のソースコード

最後にc++のソースコードを載せます

#include <iostream>

bool binarySearch(int numbers[],int length,int key){
    int left = 0;
    int right = length;
    int center;
    
    while(left < right){
        center = (left + right) / 2;
        if(key == numbers[center]) return true;
        else if(key > numbers[center]) left = center + 1;
        else right = center;
    }
    return false;
}

int main(int argc, const char * argv[]) {
    int numbers[] = {2,4,6,8,10,12,14,16,18,20};
    printf("%d",binarySearch(numbers, 10, 4));
    printf("%d",binarySearch(numbers, 10, -2));
    return 0;
}