二分探索

二分探索は、ソートされた配列の中から、特定の要素を高速で見つけ出すアルゴリズムである。

線形探索（先頭から末尾まで順番に判定していく）とは桁違いの速さで、具体的には、要素数1000000のとき線形探索では1000000回の判定が必要なのに対して、二分探索ではたった20回で済む。

この20回という回数はどこから来ているのかというと、要素数を2^nで表したときのnから。判定回数は整数値なので、要素数が100なら2^7=128（7回）、要素数が1000000なら2^20=1048576（20回）となる。

まずはシンプルな二分探索を実装してみる。

import java.util.*;
import static java.lang.System.*;

public class Blog {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		int[] ar = {45,20,10,30,5,50,15,25,35,40};
		Arrays.sort(ar); //ソートする
		
		//ソートされた配列を表示
		for (int e:ar) {out.print(e+" ");} out.println();
		
		//ここから二部探索
		//L,Rを宣言
		int L = 0;
		int R = ar.length; //Rの初期値は要素数
		int target = 30;
		
		while (L < R) {
			int M = (L+R)/2;
			if (ar[M] == target) {
				out.println(target+"は"+(M+1)+"番目です");
				break;
			}
			else if (ar[M] > target) {R = M;}
			else if (ar[M] < target) {L = M+1;}
		}
	}
}

出力

次に、「target以下・target以上、target未満・targetより大きい要素はそれぞれ配列中に何個あるか」を調べる二分探索を書いてみたい。なぜこれを書く気になったかというと、以下の問題を解いたから。

C - Snuke Festival

import java.util.*;
import static java.lang.System.*;

public class Blog {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		int[] ar = {45,20,10,30,5,50,15,25,35,40};
		Arrays.sort(ar);
		for (int e:ar) {out.print(e+" ");} out.println();
		
		
		//以下
		int target = 30;
		int L = 0;
		int R = ar.length;
		while (L < R) {
			int M = (L+R)/2;
			if (ar[M] > target) {R = M;}
			else if (ar[M] <= target) {L = M+1;} //以下・以上を調べるときはこちらに等号をつける
		}
		out.println("30以下の値は"+L+"個あります");
		
		
		//以上
		target = 30;
		target--; //target以上を調べる場合は、targetから1引いたものを使う
		L = 0;
		R = ar.length;
		while (L < R) {
			int M = (L+R)/2;
			if (ar[M] > target) {R = M;}
			else if (ar[M] <= target) {L = M+1;}
		}
		out.println("30以上の値は"+(ar.length-L)+"個あります");
		
		
		
		
		
		//未満
		target = 30;
		L = 0;
		R = ar.length;
		while (L < R) {
			int M = (L+R)/2;
			if (ar[M] >= target) {R = M;} //未満・より大きいを調べるときはこちらに等号をつける
			else if (ar[M] < target) {L = M+1;}
		}
		out.println("30未満の値は"+L+"個あります");
		
		
		//より大きい
		target = 30;
		target++; //targetより大きい値の個数を調べるときは、targetに1足したものを使う
		L = 0;
		R = ar.length;
		while (L < R) {
			int M = (L+R)/2;
			if (ar[M] >= target) {R = M;} //未満・より大きいを調べるときはこちらに等号をつける
			else if (ar[M] < target) {L = M+1;}
		}
		out.println("30より大きい値は"+(ar.length-L)+"個あります");
		
		
	}
}

出力

追記：Arrays.binarySearchというメソッドを見つけた。Arrays.binarySearch(ar,n)とすることで、配列ar内にあるnの位置を戻り値として返してくれる。機能が限られているのであまり使い道はないかもしれない。ざっと調べてみたところ、配列内に同じ値がある場合はどれが検索されるか不定とあったので、重複のない配列でのみ用いるのがよさそう。