【Java】二分探索法

二分探索とは

要素がキーの昇順または降順にソートされている配列から効率よく探索を行うアルゴリズム。

要素が昇順または降順に整列された集合に対して、探索範囲の中央に位置する値と探索する値を比較し、探索する値の方が小さければ目的の値は範囲の先頭から中央の1つ前までに、探索する値の方が大きければ目的の値は範囲の中央の1つ次から最後までに存在すると判断して、次回は探索範囲を1／2に狭めて探索することを再帰的に繰返すことで目的のデータを探索するアルゴリズムです。

メリット

線形探索法に比べて探索範囲を半分に分割しながら探索を行うため、非常に高速になります。
二分探索法は最大でlog2(n)回の比較で済みます。つまり探索範囲が倍になったら探索回数が１回増えます。

デメリット

データがソートされていなければ使えません。

二分探索のコード

alg.java

class Main {
	public static void main(String[] args) {
		// 配列と見つけたい数値の用意
		int array[] = {1,2,3,4,5,6,7,8,9,10};
		int target = -2;
		
		// 二分探索プログラムを呼び出し、一致データがあるのかを判定
		int answer = search(array,target);

		if (answer == -1) {
			System.out.println("一致データなし");
		} else {
			System.out.println(answer + "番目の要素に一致します。");
		}
	}

	// 二分探索プログラム
	public static int search(int[] array, int target) {
		int head = 0;
		int tail = array.length - 1;
		int center = 0;

		while(head <= tail){
			center = (head + tail) / 2;
			if(array[center] == target){
				return center;
			}else if(array[center] < target){
				head = center + 1;
			}else{
				tail = center - 1;
			}
		}
		return -1;	
	}

}

Arraysクラスのメソッドを使った二分探索のコード

前述の二分探索コードは自前で組んだアルゴリズムになりますが、Arrayクラスのメソッドに既に定義されており、このメソッドを使えば１行で二分探索を実行できます。

- int answer = serch(array,target);
+ int answer = Arrays.binarySearch(array,target);

- if (answer == -1) {
+ if (answer < 0) {

前述のmainメソッド内のコードを上記のように訂正し、searchメソッドを削除すると同じ結果が得られます。

binarySearchメソッドの戻り値が異なるため、if文の条件式を変更しています。
binarySearchメソッドは、target（探索したい数値）が存在する場合は、指定した array における指定したtargetが入っている要素を返します。
逆にtargetに一致するデータがない場合は負の数値を返します。
targetがarray内のどの要素よりも大きい場合は、返される負の数値は最後の要素のインデックス+1、つまり前述の'array'であれば-11を返します。
targetがarray内の１つ以上の要素より小さい場合は、返される負の数値はvalueより大きい最初の要素のインデックスのビットごとの補数、つまり前述の'array'であれば-1を返します。