C言語で二分探索法を実装する方法

順番に並んだデータから特定の値を集める検索アルゴリズムであり、２部法は配列に対して用いられます。以下はＣ言語で２部法を使った実装のサンプルです。

#include <stdio.h>

// 二分法查找函数
int binarySearch(int arr[], int left, int right, int target) {
    while (left <= right) {
        int mid = left + (right - left) / 2;

        // 如果目标值等于中间值，直接返回
        if (arr[mid] == target) {
            return mid;
        }

        // 如果目标值小于中间值，在左半部分继续查找
        if (arr[mid] > target) {
            right = mid - 1;
        }

        // 如果目标值大于中间值，在右半部分继续查找
        if (arr[mid] < target) {
            left = mid + 1;
        }
    }

    // 目标值不存在于数组中，返回-1
    return -1;
}

int main() {
    int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int target = 23;
    int arrSize = sizeof(arr) / sizeof(arr[0]);

    // 在有序数组中查找目标值
    int result = binarySearch(arr, 0, arrSize - 1, target);

    if (result == -1) {
        printf("目标值 %d 不存在于数组中\n", target);
    } else {
        printf("目标值 %d 存在于数组中，索引为 %d\n", target, result);
    }

    return 0;
}

上で定義したbinarySearch()関数は二分検索を実現するために用いられています。まず、ソート済みの配列、左の境界、右の境界、そして対象の値がパラメーターとして渡されます。関数の内部では、左と右との境界値を不断に調整し、その度に中間値を取り出して対象値と比較する操作を繰り返し、対象値が発見されるか、あるいは左の境界値が右の境界値を超えるまで続けます。

main()関数では、ソート済みの配列arrを定義し、ターゲット値targetを23に設定します。その後、binarySearch()関数を呼び出して配列内のターゲット値のインデックスを検索します。最後に、返された結果に基づいて対応する情報を表示します。

上記のコードを実行すると、「目標値 23 が配列内に存在し、インデックスは 5 です。」が出力されます。