[C言語] 2分探索を再帰関数で実装するプログラムを解説

#include <stdio.h>
// 2分探索を行う再帰関数
int binarySearch(int array[], int target, int left, int right) {
    if (left > right) {
        return -1; // 見つからない場合
    }
    int mid = left + (right - left) / 2; // 中央の要素を計算
    if (array[mid] == target) {
        return mid; // 見つかった場合
    } else if (array[mid] > target) {
        return binarySearch(array, target, left, mid - 1); // 左半分を探索
    } else {
        return binarySearch(array, target, mid + 1, right); // 右半分を探索
    }
}
int main() {
    int array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int target = 7;
    int n = sizeof(array) / sizeof(array[0]);
    int result = binarySearch(array, target, 0, n - 1);
    if (result != -1) {
        printf("要素 %d はインデックス %d にあります。\n", target, result);
    } else {
        printf("要素 %d は見つかりませんでした。\n", target);
    }
    return 0;
}

要素 7 はインデックス 6 にあります。

#include <stdio.h>
#include <string.h>
// 文字列の2分探索を行う再帰関数
int binarySearchStrings(char *array[], char *target, int left, int right) {
    if (left > right) {
        return -1; // 見つからない場合
    }
    int mid = left + (right - left) / 2;
    int cmp = strcmp(array[mid], target);
    if (cmp == 0) {
        return mid; // 見つかった場合
    } else if (cmp > 0) {
        return binarySearchStrings(array, target, left, mid - 1); // 左半分を探索
    } else {
        return binarySearchStrings(array, target, mid + 1, right); // 右半分を探索
    }
}
int main() {
    char *array[] = {"apple", "banana", "cherry", "date", "fig", "grape"};
    char *target = "cherry";
    int n = sizeof(array) / sizeof(array[0]);
    int result = binarySearchStrings(array, target, 0, n - 1);
    if (result != -1) {
        printf("文字列 \"%s\" はインデックス %d にあります。\n", target, result);
    } else {
        printf("文字列 \"%s\" は見つかりませんでした。\n", target);
    }
    return 0;
}

文字列 "cherry" はインデックス 2 にあります。

#include <stdio.h>
#include <string.h>
typedef struct {
    int id;
    char name[20];
} Item;
// 構造体の2分探索を行う再帰関数
int binarySearchStruct(Item array[], int targetId, int left, int right) {
    if (left > right) {
        return -1; // 見つからない場合
    }
    int mid = left + (right - left) / 2;
    if (array[mid].id == targetId) {
        return mid; // 見つかった場合
    } else if (array[mid].id > targetId) {
        return binarySearchStruct(array, targetId, left, mid - 1); // 左半分を探索
    } else {
        return binarySearchStruct(array, targetId, mid + 1, right); // 右半分を探索
    }
}
int main() {
    Item array[] = {{1, "apple"}, {2, "banana"}, {3, "cherry"}, {4, "date"}, {5, "fig"}};
    int targetId = 3;
    int n = sizeof(array) / sizeof(array[0]);
    int result = binarySearchStruct(array, targetId, 0, n - 1);
    if (result != -1) {
        printf("ID %d のアイテムは \"%s\" です。\n", targetId, array[result].name);
    } else {
        printf("ID %d のアイテムは見つかりませんでした。\n", targetId);
    }
    return 0;
}

ID 3 のアイテムは "cherry" です。