【C言語】2分探索アルゴリズムをサンプルコード付きで解説

2023-09-102024-06-05

目次から探す

2分探索アルゴリズムの概要

2分探索アルゴリズムは、ソートされた配列やリストから特定の要素を効率的に探索するためのアルゴリズムです。

このアルゴリズムは、探索範囲を半分ずつ絞り込んでいくことで、効率的に目的の要素を見つけることができます。

2分探索アルゴリズムの実装方法

実装手順

ソートされた配列やリストを用意します。
探索範囲の始点と終点を設定します。

始点は配列の最初の要素、終点は配列の最後の要素とします。

探索範囲の中央の要素を取得します。
中央の要素と目的の要素を比較します。

もし中央の要素が目的の要素と一致した場合、探索終了です。
もし中央の要素が目的の要素よりも大きい場合、探索範囲を前半に絞り込みます。

終点を中央の要素の一つ前の要素に更新します。

もし中央の要素が目的の要素よりも小さい場合、探索範囲を後半に絞り込みます。

始点を中央の要素の一つ後の要素に更新します。

探索範囲が絞り込まれるまで、3から4の手順を繰り返します。

コードの実装

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

上記のコードは、2分探索アルゴリズムを実装したサンプルコードです。

配列 arr から目的の要素 target を探索し、見つかった場合はその要素のインデックスを返します。

見つからなかった場合は -1 を返します。