『アルゴリズム第4版』アルゴリズム2--二分検索の再帰的実現を読む
1089 ワード
二分検索の再帰的実装
-自然言語記述:コンピュータ科学において、二分検索(英語:binary search、折半検索(英語:half-interval search)とも呼ばれ、秩序配列の中で特定の要素を検索する検索アルゴリズムであり、検索プロセスは配列の中間要素から始まり、中間要素がちょうど検索する要素であれば、検索プロセスは終了する.特定の要素が中間要素より大きいか小さい場合は、配列が中間要素より大きいか小さいかの半分で検索され、最初と同じように中間要素から比較されます.ステップ配列が空の場合は、見つからないことを意味します.この検索アルゴリズムは、比較のたびに検索範囲を半分に縮小します.-Java言語の説明:1バージョン1:
バージョン2:
-自然言語記述:コンピュータ科学において、二分検索(英語:binary search、折半検索(英語:half-interval search)とも呼ばれ、秩序配列の中で特定の要素を検索する検索アルゴリズムであり、検索プロセスは配列の中間要素から始まり、中間要素がちょうど検索する要素であれば、検索プロセスは終了する.特定の要素が中間要素より大きいか小さい場合は、配列が中間要素より大きいか小さいかの半分で検索され、最初と同じように中間要素から比較されます.ステップ配列が空の場合は、見つからないことを意味します.この検索アルゴリズムは、比較のたびに検索範囲を半分に縮小します.-Java言語の説明:1バージョン1:
public static int rank(int key, int[] a){
return rank(key, a, 0, a.length-1);
}
public static int rank(int key, int [] a, int start, int end){
// key a[] , start end
if(start > end) return -1;
int mid = start + (end - start)/2;
if(key < a[mid]) return rank(key, a, start, mid -1);
else if(key > a[mid]) return rank (key, a, mid + 1, end);
esle return mid;
}
バージョン2:
public int rank(int key,int[] a){
int start = 0; int end = a.length -1;
while(start <= end){
int mid = start + (end - start)/2
if (key < a[mid]) end = mid -1;
else if (key > a[mid]) start = mid +1;
else return mid;
}
return start;
}