ももの知恵の樹

C言語アルゴリズム-二分探索法

二分探索 (Binary Search)とは

二分探索とは、予め整列されたデータに対して、中央値との比較によって探索対象データを探す方法です。整列の中央値と探索対象を比較すると、その結果で整列の左側あるいは右側だけに候補を絞ることができます。その後も同じ要領で、残った候補に対しての中央値との比較と絞り込みを繰り返していくことで、中央値またはただひとつに絞られた候補として検索対象が現れる仕組みとなります。

探索対象データが昇順または降順に整列されていない場合には、利用することができないアルゴリズムです。


二分探索の性能

二分探索は、１回の比較で探索候補の半分を絞り込むこととなります。要素数２の時の処理時間を基準にすると、要素数４でも２倍、８でも３倍、１６でも４倍という緩やかな増加となります。データ量が倍に増えても処理時間は緩やかにしか増えない事を「対数時間」といいます。

n個のデータがある場合、時間計算量は「O(log n)」と表現します。


C言語による二分探索プログラム

素数の配列を生成して、配列に対して目的の数値を二分探索します。 


#include <stdio.h>

#define ARRAY_NUM(a) (sizeof(a)/sizeof(a[0]))

/*!
 * @brief       素数の配列を作成する
 * @param[out]  array       数値格納用配列
 * @param[in]   array_size  配列最大要素数
 */
static void
array_prime_number(int *array, unsigned int array_size)
{
    int array_pos = 0; /* 格納先の位置 */
    int tmp = 0;
    int i, j;

    /* 配列を素数で満たす */
    for(i = 1; array_pos < array_size; i++){
        tmp = 0;
        for(j = 1; j <= i; j++){
          if((i % j) == 0) tmp++;
        }

        /* 素数ならば配列に格納する */
        if(tmp == 2){
            array[array_pos] = i;
            array_pos++;
        }
    }
    return;
}

/*!
 * @brief      二分探索を行う。
 * @param[in]  array      検索データ配列
 * @param[in]  array_size 配列のサイズ
 * @param[in]  target     検索対象の数値
 * @return     要素の位置。見つからなければ-1を返す。
 */
static int
binary_search(int *array, unsigned int array_size, int target)
{
    int low    = 0;
    int middle = 0;
    int high   = array_size - 1;

    while(low <= high){
        middle = (low + high) / 2;

        if(array[middle] == target){
            /* 検索対象を発見した */
            return(middle);
        }else if(array[middle] > target){
            /* 検索対象は中間より前にある */
            high = middle - 1;
        }else{
            /* 検索対象は中間より後にある */
            low = middle + 1;
        }
    }

    return(-1);
}

int
main(void)
{
    int rc = 0;
    int num[300];

    /* 素数配列を作成する */
    array_prime_number(num, ARRAY_NUM(num));

    /* 二分探索を行う */
    rc = binary_search(num, ARRAY_NUM(num), 1601);
    if(rc > 0) printf("num[%d]=%d\n", rc, num[rc]);

    return(0);
}

関連ページ