再帰5--折半検索--java

794 ワード

折り返し(二分)検索は、並べ替えられた要素に対して
表の要素が昇順に並べられていると仮定し、表の中間位置に記録されたキーワードを検索キーワードと比較し、両者が等しい場合、検索に成功します.そうでなければ、中間位置レコードを使用してテーブルを前後の2つのサブテーブルに分割し、中間位置レコードのキーワードが検索キーワードより大きい場合は、前のサブテーブルをさらに検索し、そうでなければ後のサブテーブルをさらに検索します.条件を満たすレコードが見つかり、検索が成功するまで、またはサブテーブルが存在しないまで、上記の手順を繰り返します.
public class BiSearch {
	public static int biSearch(int[] arr, int l, int r, int key){
		if(l>r) return -1;
		
		int mid = (r+l)/2;
		if(key == arr[mid]){
			return mid;
		}else if(key > arr[mid]){
			return biSearch(arr, mid+1, r, key);
		}else{
			return biSearch(arr, l, mid-1, key);
		}		
	}
	public static void main(String[] args){
		int[] arr = {1,3,5,6,10,13,31,57,68,91};
		System.out.println(biSearch(arr,0,arr.length-1,13));
		System.out.println(biSearch(arr,0,arr.length-1,12));
	}
}