内挿探索　解答ページ | Programming Place Plus　アルゴリズムとデータ構造編【探索アルゴリズム】　第５章

トップページ – アルゴリズムとデータ構造編 – 【探索アルゴリズム】第５章

問題① 🔗

問題①　対象の配列が降順にソートされている場合の内挿探索関数を作成してください。


#include <stdint.h>
#include <stdio.h>

#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))

static int* interpolation_search(int* array, size_t size, int value);

int main(void)
{
    int array[] = { 45, 40, 33, 29, 22, 10, 9, 8, 7, 4 };

    int* p = interpolation_search( array, SIZE_OF_ARRAY(array), 29 );
    if( p == NULL ){
        puts( "見つかりませんでした。" );
    }
    else{
        puts( "見つかりました。" );
    }

    return 0;
}

/*
    内挿探索

    対象の配列array は降順にソートされていることを前提としている。
*/
int* interpolation_search(int* array, size_t size, int value)
{
    int lower = 0;              // 探索範囲の下限の添字
    int upper = (int)size - 1;  // 探索範囲の上限の添字

    while( lower < upper ){  // 上限と下限が逆転したら終わり

        // 注目位置を求める
        int mid = lower + (((intmax_t)array[lower] - value) * (upper - lower)) / (array[lower] - array[upper]);

        // mid が array の有効範囲外に出てしまっていないか
        if( mid < lower || upper < mid ){
            break;
        }

        if( array[mid] == value ){
            return &array[mid];  // 目的の値を見つけたら終わり
        }
        else if( array[mid] < value ){
            lower = mid + 1;  // 次は現在の注目位置より後ろを調べるため、下限を変更
        }
        else{
            upper = mid - 1;  // 次は現在の注目位置より手前を調べるため、上限を変更
        }
    }

    return NULL;
}

実行結果：

見つかりました。

配列が昇順にソートされている場合に比べると、上下関係が逆なので、mid を計算する際に、要素の値の差を求めている部分を逆にします。

mid = lower + ((value - array[lower]) * (upper - lower)) / (array[upper] - array[lower]);  // 昇順の場合
mid = lower + ((array[lower] - value) * (upper - lower)) / (array[lower] - array[upper]);  // 降順の場合

問題② 🔗

問題②　二分探索と内挿探索で、要素の比較回数がどの程度違うか、確認するプログラムを書いて確かめてください。


変数 count を追加して、変数 mid の計算をするたびに +1 します。あとは、探索関数を抜ける直前でその値を出力すればいいでしょう。

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define ARRAY_SIZE    (10000)
#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))

static int* binary_search(int* array, size_t size, int value);
static int* interpolation_search(int* array, size_t size, int value);

int main(void)
{
    static int array[ARRAY_SIZE];

    srand((unsigned int)time(NULL));

    array[0] = 0;
    for( int i = 1; i < ARRAY_SIZE; ++i ){
        array[i] = array[i - 1] + (rand() % 10 + 1);
    }

    int target = 100;

    array[(int)(rand() * ((double)ARRAY_SIZE / (RAND_MAX + 1)))];
    binary_search( array, SIZE_OF_ARRAY(array), target );
    interpolation_search( array, SIZE_OF_ARRAY(array), target );

    return 0;
}

/*
    二分探索

    対象の配列array は昇順にソートされていることを前提としている。
*/
int* binary_search(int* array, size_t size, int value)
{
    int lower = 0;              // 探索範囲の下限の添字
    int upper = (int)size - 1;  // 探索範囲の上限の添字

    int count = 0;

    while( lower <= upper ){  // 上限と下限が逆転したら終わり

        // 中央の位置を求める
        int mid = (lower + upper) / 2;

        ++count;

        if( array[mid] == value ){
            printf("%d\n", count);
            return &array[mid];  // 目的の値を見つけたら終わり
        }
        else if( array[mid] < value ){
            lower = mid + 1;  // 次は中央より後ろを調べるため、下限を変更
        }
        else{
            upper = mid - 1;  // 次は中央より手前を調べるため、上限を変更
        }
    }

    printf("%d\n", count);
    return NULL;
}

/*
    内挿探索

    対象の配列array は昇順にソートされていることを前提としている。
*/
int* interpolation_search(int* array, size_t size, int value)
{
    int lower = 0;              // 探索範囲の下限の添字
    int upper = (int)size - 1;  // 探索範囲の上限の添字

    int count = 0;

    while( lower < upper ){  // 上限と下限が逆転したら終わり

        // 注目位置を求める
    #if 1
        // データ列内の値の重複に備える
        int d = array[upper] - array[lower];
        if(d == 0){
            d = 1;
        }
        int mid = lower + (((intmax_t)value - array[lower]) * (upper - lower)) / d;
    #else
        // データ列内の値の重複に備えない
        int mid = lower + (((intmax_t)value - array[lower]) * (upper - lower)) / (array[upper] - array[lower]);
    #endif

        ++count;

        // mid が array の有効範囲外に出てしまっていないか
        if( mid < lower || upper < mid ){
            break;
        }

        if( array[mid] == value ){
            printf("%d\n", count);
            return &array[mid];  // 目的の値を見つけたら終わり
        }
        else if( array[mid] < value ){
            lower = mid + 1;  // 次は現在の注目位置より後ろを調べるため、下限を変更
        }
        else{
            upper = mid - 1;  // 次は現在の注目位置より手前を調べるため、上限を変更
        }
    }

    printf("%d\n", count);
    return NULL;
}

実行結果：

14
3

データ列の内容や、探索する値によって回数は増減するので、何度か試してみる必要があります。それでも傾向として、データ数を 10倍にしていくたび、二分探索の比較回数はじわじわ増えていきますが、内挿探索ではほとんど変わらないことが分かるはずです。

データ件数を変えて試すとこうなりました。

データ件数 binary_search interpolation_search
10000個 14回 3回
100000個 17回 4回
1000000個 19回 4回

内挿探索の圧倒的な効率の良さがうかがえます。しかし本編で触れたとおり、内挿探索は極度に性能が悪くなるケースがありますから注意が必要です。

内挿探索の性能が極端に落ちるように、配列の初期化部分を次のように変えて試します。

array[0] = 0;
for( int i = 1; i < ARRAY_SIZE - 1; ++i ){
    array[i] = array[i - 1] + (rand() % 10 + 1);
}
array[ARRAY_SIZE - 1] = INT_MAX;

すると、比較回数はこうなります。内挿探索はかなり変動が激しいので、1000回ほど繰り返して、最小回数と最大回数を調べた結果になっています。

データ件数 binary_search interpolation_search
10000個 12回 8～9995回
100000個 16回 52～32723回
1000000個 20回 426～36011回

内挿探索が極度に性能を落とすとき、このように比較回数が激増しています。


参考リンク 🔗


更新履歴 🔗

　各サンプルプログラムにおいて、存在する要素を見つけられないことがあったのを修正。
変数mid が配列の範囲外を指していないかどうかのチェックが間違っていた。
問題①の解答例を修正。

≪さらに古い更新履歴を展開する≫


第５章のメインページへ

アルゴリズムとデータ構造編のトップページへ

Programming Place Plus のトップページへ

はてなブックマーク に保存 Pocket に保存 Facebook でシェア
X で ポスト／フォロー LINE で送る noteで書く
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー
先頭へ戻る