目次から探す
二分探索の概要
※二分探索は、ソートされた配列やリストを対象に、中央の要素を基準に探索範囲を半分に絞り込んでいく手法です。
二分探索のアルゴリズム
※以下に、二分探索のアルゴリズムの手順を示します。
- 探索範囲の始点と終点を設定する。
- 探索範囲の中央の要素を取得する。
- 中央の要素と目的の要素を比較する。
- 中央の要素が目的の要素と一致した場合、探索終了。
- 中央の要素が目的の要素よりも大きい場合、探索範囲を前半に絞り込む。
- 中央の要素が目的の要素よりも小さい場合、探索範囲を後半に絞り込む。
- 探索範囲が絞り込めなくなるまで、2から6の手順を繰り返す。
C言語での二分探索の実装
※以下に、C言語での二分探索の実装例を示します。
#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