二分探索　解答ページ | 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 = (int)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文の条件式を変えるだけで、降順に対応したものになります。

問題② 🔗

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


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

#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 = (int)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関数を使います。この関数は、２つの文字列が完全に一致していれば 0 を、第１引数の方が辞書順で先に来るなら負数を、第２引数の方が先に来るなら 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, (int)(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;
}

実行結果：

見つかりました。


参考リンク 🔗


更新履歴 🔗

　SIZE_OF_ARRAYマクロの定義を修正。

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

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

　新規作成。


第４章のメインページへ

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

Programming Place Plus のトップページへ

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