再帰二分法検索
660 ワード
二分法検索は秩序配列に対する検索に確立され,ここでは再帰的なアルゴリズムを用い,アルゴリズム自体は比較的簡単であるが,ここでは述べない.
二分法検索の時間効率はO(log n)である.
コードは次のとおりです.
二分法検索の時間効率は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);
}
}