【C言語】bsearchの使い方｜構造体・配列での二分探索のやり方

void *bsearch(
    const void *key,      // 探したいキー(検索対象の値)
    const void *base,     // 先頭要素へのポインタ(配列の先頭)
    size_t nmemb,         // 配列の要素数
    size_t size,          // 各要素のサイズ(バイト数)
    int (*compar)(        // 比較関数へのポインタ
        const void *a,
        const void *b
    )
);

#include <stdio.h>
#include <stdlib.h>

// int用の比較関数
// a < b のとき負の値、a == b のとき0、a > b のとき正の値を返す
int compare_int(const void *a, const void *b) {
    // voidポインタをintポインタにキャストしてから中身を参照
    int ia = *(const int *)a;
    int ib = *(const int *)b;

    if (ia < ib) return -1;
    if (ia > ib) return 1;
    return 0;
}

int main(void) {
    // 昇順にソート済みの配列とする
    int arr[] = {1, 3, 5, 7, 9, 11, 13};
    int n = (int)(sizeof(arr) / sizeof(arr[0]));

    int key = 7;  // 探したい値

    // bsearch呼び出し
    // key: &key
    // base: arr
    // nmemb: n
    // size: sizeof(int)
    // compar: compare_int
    int *found = bsearch(
        &key,
        arr,
        (size_t)n,
        sizeof(int),
        compare_int
    );

    if (found != NULL) {
        int index = (int)(found - arr);  // 見つかった要素のインデックス計算
        printf("値%dがインデックス%dで見つかりました。\n", key, index);
    } else {
        printf("値%dは配列内に存在しません。\n", key);
    }

    return 0;
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 文字列(チャーポインタ)用の比較関数
int compare_str(const void *a, const void *b) {
    // a, b は「char *」へのポインタ、すなわち「char **」として扱う
    const char *sa = *(const char * const *)a;
    const char *sb = *(const char * const *)b;

    // strcmpの返り値をそのまま使う
    return strcmp(sa, sb);
}

int main(void) {
    // 辞書順(ASCII順)にソート済みとする
    const char *words[] = {
        "apple",
        "banana",
        "grape",
        "orange",
        "peach"
    };
    int n = (int)(sizeof(words) / sizeof(words[0]));

    const char *key = "grape";

    // bsearchで文字列を探索
    const char **found = bsearch(
        &key,               // keyも「char *」へのポインタなので「&key」
        words,              // 配列の先頭
        (size_t)n,
        sizeof(char *),     // 要素は「char *」なのでそのサイズ
        compare_str
    );

    if (found != NULL) {
        int index = (int)(found - words);
        printf("%s はインデックス%dで見つかりました。\n", key, index);
    } else {
        printf("%s は配列内に存在しません。\n", key);
    }

    return 0;
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int id;
    char name[32];
} Person;

// Person構造体をidで比較する関数
int compare_person_by_id(const void *a, const void *b) {
    const Person *pa = (const Person *)a;
    const Person *pb = (const Person *)b;

    if (pa->id < pb->id) return -1;
    if (pa->id > pb->id) return 1;
    return 0;
}

int main(void) {
    // idの昇順にソート済みの配列とする
    Person people[] = {
        {1, "Alice"},
        {3, "Bob"},
        {5, "Charlie"},
        {7, "Diana"}
    };
    int n = (int)(sizeof(people) / sizeof(people[0]));

    // 「idだけ」が入った一時的なキー用構造体を作る
    Person key;
    key.id = 5;

    // bsearch呼び出し
    Person *found = bsearch(
        &key,                   // key構造体
        people,                 // 配列先頭
        (size_t)n,
        sizeof(Person),         // 要素サイズ
        compare_person_by_id    // idで比較
    );

    if (found != NULL) {
        int index = (int)(found - people);
        printf("id=%d の人物は %s (インデックス%d) です。\n",
               key.id, found->name, index);
    } else {
        printf("id=%d の人物は見つかりませんでした。\n", key.id);
    }

    return 0;
}

#include <stdio.h>
#include <stdlib.h>

// int用の比較関数(前と同じ)
int compare_int(const void *a, const void *b) {
    int ia = *(const int *)a;
    int ib = *(const int *)b;
    if (ia < ib) return -1;
    if (ia > ib) return 1;
    return 0;
}

int main(void) {
    int arr[] = {42, 7, 13, 99, 5, 28};
    int n = (int)(sizeof(arr) / sizeof(arr[0]));

    // まずqsortで昇順にソート
    qsort(
        arr,
        (size_t)n,
        sizeof(int),
        compare_int
    );

    // ソート結果を表示
    printf("ソート後の配列: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    int key = 28;

    // ソートに使ったのと同じ比較関数でbsearchを呼ぶ
    int *found = bsearch(
        &key,
        arr,
        (size_t)n,
        sizeof(int),
        compare_int
    );

    if (found != NULL) {
        int index = (int)(found - arr);
        printf("値%dがインデックス%dで見つかりました。\n", key, index);
    } else {
        printf("値%dは配列内に存在しません。\n", key);
    }

    return 0;
}