【C言語】二分探索（バイナリサーチ）で配列内の最小要素を見つける方法

C言語には、目的のデータを効率よく見つけ出すための探索アルゴリズムとして、主に次の2つの手法が用意されています。

• 線形探索（リニアサーチ）
• 二分探索（バイナリサーチ）

二分探索（バイナリサーチ）とは

• この手法はソート済み（整列済み）のリストにのみ適用できます。
• 対象のリストを半分ずつに分割しながら、探索範囲を絞り込んでいきます。
• 探したいキーと、リスト中央の要素を比較します。

比較の結果、次の3つの場合が考えられます。

• 中央の要素がキーと一致した場合 → 探索は成功し、その時点で終了します。

• 中央の要素がキーより大きい場合 → 左側の領域で探索を続けます。

• 中央の要素がキーより小さい場合 → 右側の領域で探索を続けます。

入力：要素のリストとキー
出力：

• 成功 – キーが見つかった場合
• 失敗 – 見つからなかった場合

たとえば key = 20 を探す場合、中央位置 mid は「(low + high) / 2」で計算されます。

key = 20
mid = (low + high) / 2

※なお、二分探索はソート済みのデータが前提となるため、実際に使用する際はあらかじめ配列を昇順に並べ替えておく必要があります。

プログラム1：二分探索でキーを検索するCプログラム

以下は、二分探索の基本動作を確認できるCプログラムです。入力されたキーが配列内に存在するかどうかを判定し、結果を表示します。

#include<stdio.h>
int main(){
    int a[50], n, i, key, flag = 0, low, mid, high;
    printf("要素数を入力してください：");
    scanf("%d", &n);
    printf("要素を入力してください：");
    for(i = 0; i < n; i++)
        scanf("%d", &a[i]);
    printf("探したいキーを入力してください：");
    scanf("%d", &key);
    low = 0;
    high = n - 1;
    while(low <= high){
        mid = (low + high) / 2;
        if(a[mid] == key){
            flag = 1;
            break;
        }else{
            if(a[mid] > key)
                high = mid - 1;
            else
                low = mid + 1;
        }
    }
    if(flag == 1)
        printf("探索成功：キーが見つかりました\n");
    else
        printf("探索失敗：キーは見つかりませんでした\n");
    return 0;
}

実行結果

上記プログラムを実行すると、次のような結果になります。

実行例1：
要素数を入力してください：5
要素を入力してください：
12
34
11
56
67
探したいキーを入力してください：45
探索失敗：キーは見つかりませんでした

実行例2：
要素数を入力してください：3
要素を入力してください：
12
34
56
探したいキーを入力してください：34
探索成功：キーが見つかりました

プログラム2：二分木（ヒープ）の考え方で配列の最小値を求めるCプログラム

次に、配列内の最小要素を求めるCプログラムを紹介します。関数名は binarysearchmin ですが、実際には配列を完全二分木（ヒープ）として扱い、根の要素に最小値が来るように再配置することで最小値を取得しています。

配列は添字1から格納し、「要素 i の子は 2i と 2i+1」という親子関係を利用してヒープを構築します。すべての内部ノードに対して Bmin() を呼び出せば、最終的に根 a[1] に最小値が残る仕組みです。

#include<stdio.h>
void Bmin(int *a, int i, int n){
    int j, temp;
    temp = a[i];
    j = 2 * i;
    while(j <= n){
        if(j < n && a[j+1] > a[j])
            j = j + 1;
        if(temp < a[j])
            break;
        else if(temp >= a[j]){
            a[j / 2] = a[j];
            j = 2 * j;
        }
    }
    a[j / 2] = temp;
    return;
}
int binarysearchmin(int *a, int n){
    int i;
    for(i = n / 2; i >= 1; i--){
        Bmin(a, i, n);
    }
    return a[1];
}
int main(){
    int n, i, x, min;
    int a[20];
    printf("配列の要素数を入力してください\n");
    scanf("%d", &n);
    printf("\n%d個の要素を入力してください：", n);
    for(i = 1; i <= n; i++){
        scanf("%d", &a[i]);
    }
    min = binarysearchmin(a, n);
    printf("\n配列の最小要素は：%d\n", min);
    return 0;
}

実行結果

上記プログラムを実行すると、次のような結果になります。

配列の要素数を入力してください
5

5個の要素を入力してください：
12
23
34
45
56

配列の最小要素は：12

まとめ

二分探索は、ソート済みデータを対象に探索範囲を半分ずつ絞り込むことで高速な検索を実現するアルゴリズムです。さらに、配列を二分木（ヒープ）として捉えることで、最小値や最大値の抽出にも応用できます。それぞれの特徴を理解し、用途に応じて使い分けることで、C言語でのデータ処理をより効率的に行えるようになります。