『アルゴリズム第4版』アルゴリズム2--二分検索の再帰的実現を読む

1089 ワード

二分検索の再帰的実装
-自然言語記述:コンピュータ科学において、二分検索(英語: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;
  }