アルゴリズム

二分探索

更新日:

二分探索のアルゴリズム

代表的な探索のアルゴリズムです。

これを使う条件として、探索したい要素を含んだ列がソートしてある必要があります。

二分探索の動きを見ていきましょう。

二分探索は探索範囲の真ん中の値と探索する値を比較し、その大小で探索範囲を絞り込んでいきます。

例を見てみましょう。
以下の配列i[]から3を探します。

i[0] i[1] i[2] i[3] i[4] i[5] i[6] i[7] i[8] i[9]
0 3 5 7 8 10 11 15 21 22

まず真ん中の値(偶数個ならどちらか)であるi[5]と探索値3を比較します。
3はi[5]よりも小さいのでi[5]以降にはありません。
よって探索範囲をi[0]からi[4]に変更します。

同様に3とi[2]を比較するとi[2]の方が大きいので探索範囲をi[0]からi[1]にします。

最後にi[3]と3を比較するとこれは一致します。

以上が二分探索のアルゴリズムです。

ソースコード

以下が二分探索のソースコードの例です。

binary_search_sample1.c

#include 

int main(void)
{
	int a[] = { 0,1,2,3,4,5,6,7,8,9 };

	int serch = 3;

	int right = 0, left = 9;

	while (right < left)
	{
		printf("a");
		int mid = (left + right) / 2;

		if (serch == a[mid])
		{
			printf("%dは%d番目", serch, mid);
			break;
		}
		else if (serch > a[mid])
			right = mid;
		else if (serch < a[mid])
			left = mid;
	}
	return 0;
}



-アルゴリズム

Copyright© C言語/C++入門講座  ツナサーモン , 2019 All Rights Reserved Powered by AFFINGER5.