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

目次から探す

2分探索の概要

※2分探索は、ソートされた配列やリストを対象に、中央の要素を基準に探索範囲を半分に絞り込んでいく手法です。

2分探索のアルゴリズム

※以下に、2分探索のアルゴリズムの手順を示します。

  1. 探索範囲の始点と終点を設定する。
  2. 探索範囲の中央の要素を取得する。
  3. 中央の要素と目的の要素を比較する。
  4. 中央の要素が目的の要素と一致した場合、探索終了。
  5. 中央の要素が目的の要素よりも大きい場合、探索範囲を前半に絞り込む。
  6. 中央の要素が目的の要素よりも小さい場合、探索範囲を後半に絞り込む。
  7. 探索範囲が絞り込めなくなるまで、2から6の手順を繰り返す。

C言語での2分探索の実装

※以下に、C言語での2分探索の実装例を示します。

#include <stdio.h>
int binarySearch(char arr[], int start, int end, char target) {
    while (start <= end) {
        int mid = start + (end - start) / 2;
        if (arr[mid] == target) {
            return mid;
        }
        if (arr[mid] < target) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    return -1;
}
int main() {
    char arr[] = {'a', 'b', 'c', 'd', 'e', 'f', 'g'};
    int size = sizeof(arr) / sizeof(arr[0]);
    char target = 'c';
    int result = binarySearch(arr, 0, size - 1, target);
    if (result == -1) {
        printf("要素が見つかりませんでした。\n");
    } else {
        printf("要素が見つかりました。インデックス: %d\n", result);
    }
    return 0;
}

※上記のコードを実行した場合の結果は以下の通りです。

要素が見つかりました。インデックス: 2

目次から探す