二分探索実装・詳しい計算量解説

2025/02/02

二分探索(Binary Search)

二分探索は、あらかじめ整列された配列（またはリスト）の中から目的の値を高速に探索するアルゴリズムです。

探索のたびに候補範囲を半分に絞ることで、探索に必要な操作回数は対数的に減少し、非常に効率が良いのが特徴です。

本記事では、二分探索のアルゴリズムの解説、C 言語での実装例、および計算量の議論について詳しく説明します。

二分探索の基本的な手順は以下の通りです。

配列の先頭と末尾のインデックスをそれぞれ left と right として設定する。
left と right の中央に位置する mid の値を求め、配列[mid] と目的の値 target を比較する。
配列[mid] が target と等しければ探索を終了する。
target が配列[mid] より大きければ探索範囲を右半分に絞り、逆に小さければ左半分に絞る。
探索範囲がなくなるまで 2 ～ 4 を繰り返す。

このアルゴリズムは、毎回探索対象が半分に削減されるため、比較回数は対数的に増加し、計算量は $O(\log N)$ となります。

C 言語での実装例

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

 
#include <stdio.h>
int binarySearch(int arr, int n, int target) {
	int left = 0, right = n - 1;
	while (left <= right) {
		int mid = left + (right - left) / 2;
		if (arr[mid] == target) {
			return mid; // 目的の値が見つかった場合、そのインデックスを返す
		} else if (arr[mid] < target) {
			left = mid + 1; // 目的の値は右側にある
		} else {
			right = mid - 1; // 目的の値は左側にある
		}
	}
	return -1; // 目的の値が存在しなかった場合
}
 
int main(void) {
	int data[] = {1, 3, 5, 7, 9, 11, 13};
	int n = sizeof(data) / sizeof(data[0]);
	int target = 7;
	int index = binarySearch(data, n, target);
	if (index != -1) {
		printf("値 %d はインデックス %d に存在します。\n", target, index);
	} else {
		printf("値 %d は配列内に存在しません。\n", target);
	}
	return 0;
}