先頭へ戻る

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

Programming Place Plus トップページ -- アルゴリズムとデータ構造編

先頭へ戻る

問題①

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


#include <stdio.h>

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

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

int main(void)
{
    int array[] = { 16, 9, 7, 3, 0, -1, -4 };

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

    return 0;
}

/*
    二分探索

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

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

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

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

    return NULL;
}

実行結果:

見つかりました。

本編の最初のサンプルプログラムを変更しました。binary_search関数の中で、if文の条件式を変えるだけで、降順に対応したものになります。

実用的にいえば、データが降順に並んでいるよりも、昇順に並んでいることの方が多いため、それに合わせて昇順対応版をデフォルトとして、降順版をオプションとして用意します。比較処理の部分を取り替えられるように実装すると良いでしょう。そのような実装をするためには、第1章の練習問題②にあるように、関数ポインタ(C言語編第38章参照)を使えます。

問題②

問題② 対象の配列の要素が文字列の場合でも二分探索が使えますか? 可能ならば実装してみてください。


文字列としてソート済みであれば、二分探索を適用することはもちろん可能です。

#include <stdio.h>
#include <string.h>

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

static const char* binary_search(const char* const* array, size_t size, const char* target);

int main(void)
{
    const char* const array[] = {
        "red",
        "blue",
        "green",
        "white",
        "black",
    };

    const char* p = binary_search( array, SIZE_OF_ARRAY(array), "white" );
    if( p == NULL ){
        puts( "見つかりませんでした。" );
    }
    else{
        puts( "見つかりました。" );
    }

    return 0;
}

/*
    二分探索

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

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

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

        int cmp_result = strcmp(array[mid], target);
        if( cmp_result == 0 ){
            return array[mid];  // 目的の値を見つけたら終わり
        }
        else if( cmp_result < 0 ){
            lower = mid + 1;  // 次は中央より後ろを調べるため、下限を変更
        }
        else{
            upper = mid - 1;  // 次は中央より手前を調べるため、上限を変更
        }
    }

    return NULL;
}

実行結果:

見つかりました。

文字列同士の比較処理を必要としますから、strcmp関数を使います。この関数は、2つの文字列が完全に一致していれば 0 を、第1引数の方が辞書順で先に来るなら負数を、第2引数の方が先に来るなら 1以上の整数を返します。

問題③

問題③ 引数に、配列と探索範囲の上限と下限、探索する値を指定する形で二分探索関数を作成してください。


#include <stdio.h>

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

static int* binary_search(int* array, int lower, int upper, int value);

int main(void)
{
    int array[] = { -4, -1, 0, 3, 7, 9, 16 };

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

    return 0;
}

/*
    二分探索

    対象の配列array は昇順にソートされていることを前提としている。
*/
int* binary_search(int* array, int lower, int upper, int value)
{
    while( lower <= upper ){  // 上限と下限が逆転したら終わり

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

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

    return NULL;
}

実行結果:

見つかりました。

本編のサンプルプログラムでは、配列と要素数、探索する値を渡す形式ばかりを取り上げましたが、そのような引数の組み合わせはC言語的とも言えます。つまり、配列の要素がメモリ上に連続的に並んでいることに依存しています。その意味では、この問題のように、上限と下限の位置を渡す形式の方が汎用的な実装とも言えます。


参考リンク


------------------------------------------------------------------------

更新履歴

'2015/12/27 SIZE_OF_ARRAYマクロの定義を修正。

'2015/2/21 サンプルプログラムで、ファイルスコープでよい関数に static を付加。

'2015/1/17 問題①のプログラムで、binary_search関数のコメントが、昇順版のままになっていたのを修正。

'2012/1/21 新規作成。



第4章のメインページへ

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

Programming Place Plus のトップページへ



はてなブックマーク に保存 Pocket に保存 Facebook でシェア
Twitter でツイート Twitter をフォロー LINE で送る
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー