二分探索

ホームアルゴリズム入門講座 > 二分探索

二分探索

二分探索の基本データ

二分探索のアルゴリズム

二分探索は「ソートされたデータ」に対しては極めて強力な威力を発揮するアルゴリズムです。

二分探索は考え方としてはマージソートやクイックソートなどの分割統治法に近く、計算量も O(log n) です。まず、配列はソートされているとします。そして、配列の中央値をとります。この値と探索する値を比較し、探索する値の方が大きければ右を、小さければ左を探していきます。

1 2 3 4 5 6 7 8 9
から 8 を探索する

まず、中央値 5 をとる
8 は 5 より大きいので、今度は
6 7 8 9
から 8 を探索する

まず、中央値 7 をとる
8 は 7 より大きいので、今度は
8 9
から 8 を探索する

まず、中央値 8 をとる
8 は 8 と等しいので、探索に成功した

元のデータがソートされていることを前提に二分していくことで、消去法を用いて探索していきます。

二分探索の実装

using System;

namespace NewWorld
{
	class MainClass
	{
		private static int count = 0;
		public static void Main(string[] args)
		{
			int[] data = {6,3,8,5,4,7,9,2,1};
			QuickSort(data,0,data.Length-1);
			int indexof = IndexOf(data,7);
			
			foreach(int i in data)
				Console.Write(i + " ");
			Console.WriteLine();
			Console.WriteLine("index = {0}", indexof);
			Console.WriteLine("{0} times", count);
		}
		
		public static int IndexOf(int[] data, int search_number)
		{
			int start = 0;
			int end = data.Length - 1;
			int indexof = -2;
			int center;
			
			if(search_number < data[start] || data[end] < search_number) return -1;
			
			while(indexof == -2)
			{
				count++;
				
				center = (start + end) / 2;
				if (data[center] == search_number) indexof = center;
				else if (end - start == 1 && data[end] == search_number) indexof = end;
				else if (end - start == 1) indexof = -1;
				else if (search_number < data[center]) end = center;
				else if (data[center] < search_number) start = center;
			}
			return indexof;
			
		}

		// QuickSort
		public static void QuickSort(int[] basedata, int start, int end)
		{
			int p = basedata[(start + end) / 2];
			int i = start;
			int y = end;
			int m;
			
			while(i < y && (end - start) > 1)
			{
				while(basedata[i] < p) i++;
				while(p < basedata[y]) y--;
				
				m = basedata[i];
				basedata[i] = basedata[y];
				basedata[y] = m;
				
				if(i < end) i++;
				if(start < y) y--;
			}
			if(start + 1 < i) QuickSort(basedata, start, i - 1);
			if(y < end - 1) QuickSort(basedata, y + 1, end);
		}
	}
}

二分探索ではあらかじめソートされていることを前提にしていますので、クイックソートのメソッドも掲載しました。最初の配列とソート後の配列の index はバラバラになっています。

アルゴリズム自体は単純ですが、私が二分探索アルゴリズムを実装する際は、何度も無限ループに引っかかり、苦労しました。そのおもな理由は、終了条件です。

アルゴリズム自体ではいずれ「中央値」にヒットするはずですが、値がない場合も考慮に入れなければなりません。「値がない」ことをどのように判断するかはとても重要です。

二分探索を実装する際は様々な方法が考えられますが、ここでは私が独自に実装した上のサンプルを用いて説明します。

まず、最初の終了条件として、「配列の範囲外」ということが考えられます。そもそもソートされた配列の最初の値より小さかったり、最後の値より大きかったりする場合は、二分をする以前に値がないことをキャッチできます。

次に、「中央値」と「探索する値」が一致したときも終了します。これは成功した場合の終了です。

さらに忘れてはいけないのが、探索する範囲が2つにまでしぼられたときです。

center = (start + end) / 2
で、
end - start = 1 (たとえば start = 7, end = 8 のとき)
のとき、
end = start + 1
であり、
center = (start + (start + 1)) / 2
       = start + 0.5
となるので、center は int 型で0.5は切り捨てられ、
center = start
となる。

探索する値が center よりも大きい場合は
start = center
であるから、このアルゴリズムは無限にループする

私はこの無限ループで何度もパソコンがヒートアップしそうになりました。この問題を解決するにはいろいろな方法がありますが、私は以下のような方法を使いました。

探索する範囲が2つにしぼられたときを考える
また、2つの要素を start と end と決める

上記の考察から、start に関しては center と一致するので通常の探索でキャッチできる
探索する値が start(center) よりも大きい場合、
・end と一致するなら、探索する値は end である
・end と一致しないなら、探索する値は存在しない
と考えることができる

要するに、範囲が2つにしぼられたら1つは自動的に調べられますが、もう片方も調べてしまおうと言うものです。

もしかしたら、start や end を変更する際のアルゴリズムに手を加えればこのような回りくどい処理が不要になるのかもしれません。そこはみなさんで研究してください。