[C言語] 任意の文字列を2分探索で検索する方法を解説

#include <stdio.h>
int binarySearch(int arr[], int size, int target) {
    int left = 0;
    int right = size - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        // 中央の要素とターゲットを比較
        if (arr[mid] == target) {
            return mid; // 見つかった場合、インデックスを返す
        }
        if (arr[mid] < target) {
            left = mid + 1; // 右半分を探索
        } else {
            right = mid - 1; // 左半分を探索
        }
    }
    return -1; // 見つからなかった場合
}
int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 5;
    int result = binarySearch(arr, size, target);
    if (result != -1) {
        printf("要素はインデックス %d にあります。\n", result);
    } else {
        printf("要素が見つかりませんでした。\n");
    }
    return 0;
}

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

#include <stdio.h>
#include <string.h>
int binarySearchStrings(char *arr[], int size, char *target) {
    int left = 0;
    int right = size - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        int cmp = strcmp(arr[mid], target);
        // 中央の文字列とターゲットを比較
        if (cmp == 0) {
            return mid; // 見つかった場合、インデックスを返す
        }
        if (cmp < 0) {
            left = mid + 1; // 右半分を探索
        } else {
            right = mid - 1; // 左半分を探索
        }
    }
    return -1; // 見つからなかった場合
}
int main() {
    char *arr[] = {"apple", "banana", "cherry", "date", "fig", "grape"};
    int size = sizeof(arr) / sizeof(arr[0]);
    char *target = "cherry";
    int result = binarySearchStrings(arr, size, target);
    if (result != -1) {
        printf("文字列はインデックス %d にあります。\n", result);
    } else {
        printf("文字列が見つかりませんでした。\n");
    }
    return 0;
}

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

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 文字列比較関数
int compareStrings(const void *a, const void *b) {
    return strcmp(*(const char **)a, *(const char **)b);
}
int main() {
    char *arr[] = {"banana", "apple", "grape", "cherry", "fig", "date"};
    int size = sizeof(arr) / sizeof(arr[0]);
    // 配列をソート
    qsort(arr, size, sizeof(char *), compareStrings);
    // ソート結果を表示
    for (int i = 0; i < size; i++) {
        printf("%s\n", arr[i]);
    }
    return 0;
}

apple
banana
cherry
date
fig
grape

#include <stdio.h>
#include <string.h>
// 2分探索関数(前述のコードを再利用)
int binarySearchStrings(char *arr[], int size, char *target) {
    int left = 0;
    int right = size - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        int cmp = strcmp(arr[mid], target);
        if (cmp == 0) {
            return mid;
        }
        if (cmp < 0) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}
int main() {
    char *arr[] = {"apple", "banana", "cherry", "date", "fig", "grape"};
    int size = sizeof(arr) / sizeof(arr[0]);
    char *target = "cherry";
    int result = binarySearchStrings(arr, size, target);
    if (result != -1) {
        printf("文字列はインデックス %d にあります。\n", result);
    } else {
        printf("文字列が見つかりませんでした。\n");
    }
    return 0;
}

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