再帰二分法検索

660 ワード

二分法検索は秩序配列に対する検索に確立され,ここでは再帰的なアルゴリズムを用い,アルゴリズム自体は比較的簡単であるが,ここでは述べない.
二分法検索の時間効率はO(log n)である.
コードは次のとおりです.
class BinarySearch {
	public static void main(String[] args) {
		int[] a = {2,3,4,5,6,7,8,9,10,13,17,18,24,56,78};
		System.out.println(search(a,5));
	}

	private static int search(int[] a, int key) {
		return search(a,0,a.length,key);
	}

	private static int search(int[] a, int from, int to, int key) {
		if(from > to) return -1;
		int middle = (from + to)/2;
		if (a[middle] == key) return middle;
		if (a[middle] > key) return search(a,from,middle-1,key);
		else return search(a,middle+1,to,key);
	}
}