再帰5--折半検索--java
794 ワード
折り返し(二分)検索は、並べ替えられた要素に対して
表の要素が昇順に並べられていると仮定し、表の中間位置に記録されたキーワードを検索キーワードと比較し、両者が等しい場合、検索に成功します.そうでなければ、中間位置レコードを使用してテーブルを前後の2つのサブテーブルに分割し、中間位置レコードのキーワードが検索キーワードより大きい場合は、前のサブテーブルをさらに検索し、そうでなければ後のサブテーブルをさらに検索します.条件を満たすレコードが見つかり、検索が成功するまで、またはサブテーブルが存在しないまで、上記の手順を繰り返します.
表の要素が昇順に並べられていると仮定し、表の中間位置に記録されたキーワードを検索キーワードと比較し、両者が等しい場合、検索に成功します.そうでなければ、中間位置レコードを使用してテーブルを前後の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));
}
}