目次から探す
二分探索アルゴリズムの概要
二分探索アルゴリズムは、ソートされた配列やリストから特定の要素を効率的に探索するためのアルゴリズムです。
このアルゴリズムは、探索範囲を半分ずつ絞り込んでいくことで、効率的に目的の要素を見つけることができます。
二分探索アルゴリズムの実装方法
実装手順
- ソートされた配列やリストを用意します。
- 探索範囲の始点と終点を設定します。
始点は配列の最初の要素、終点は配列の最後の要素とします。
- 探索範囲の中央の要素を取得します。
- 中央の要素と目的の要素を比較します。
- もし中央の要素が目的の要素と一致した場合、探索終了です。
- もし中央の要素が目的の要素よりも大きい場合、探索範囲を前半に絞り込みます。
終点を中央の要素の一つ前の要素に更新します。
- もし中央の要素が目的の要素よりも小さい場合、探索範囲を後半に絞り込みます。
始点を中央の要素の一つ後の要素に更新します。
- 探索範囲が絞り込まれるまで、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;
}上記のコードは、二分探索アルゴリズムを実装したサンプルコードです。
配列 arr から目的の要素 target を探索し、見つかった場合はその要素のインデックスを返します。
見つからなかった場合は -1 を返します。
二分探索アルゴリズムの応用例
二分探索アルゴリズムは、ソートされたデータの中から特定の要素を高速に探索するため、様々な応用があります。
例えば、辞書の単語リストから特定の単語を探す、数値の範囲内での最大値や最小値を求める、ソートされた配列内での重複要素の検出などに利用することができます。
ソートされていないデータに対しては、事前にソート処理を行う必要があります。
また、二分探索アルゴリズムは効率的な探索手法ですが、データの挿入や削除が頻繁に行われる場合には適していません。