折半検索(二分検索)の応用とテクニックの全面的な総括

6127 ワード

c アルゴリズム半値で検索

半角検索はアルゴリズムの中で比較的に簡単でよく見られるが、実用的な方法の一つであり、二分検索とも呼ばれ、その応用は比較的広く、配列中の要素の検索をソートするのに使用することができ、複雑度はlog(N)だけで、秩序配列中の要素の挿入などにも使用することができる.一般的に並べ替え配列に対するいくつかのアルゴリズムは、折りたたみ探索の折りたたみ探索の思想に多くまたは少なく用いられ、折りたたみ探索の実現は主に2つの方式に分けられ、1つは非再帰形式を遍歴し、1つは再帰形式を採用する.
1、非再帰形式であり、このような実現は主に中点の位置を調整するたびに実現される.

int binsearch1(int arr[], int k, int l, int h){
        if(l > h){
                return -1;
        }
        int mid;
        while(l <= h){
                mid = (l + h) / 2;
                if(k == arr[mid]){
                        return mid;
                }else if(k > arr[mid]){
                        l = mid + 1;
                }else{
                        h = mid - 1;
                }
        }
        return -1;
}

この方法は柔軟ですが、多くの変形の問題を解決するのに役立ちます.後で紹介します.
2、再帰の形式、この形式は比較的に簡単で、起点、中点、終点の位置を調整して、再帰関数は実現することができます

int binsearch2(int arr[], int k, int l, int h){
        if(l > h){
                return -1;
        }
        int mid = (l + h) / 2;
        if(k == arr[mid]){
                return mid;
        }else  if(k > arr[mid]){
                binsearch2(arr, k, mid +1, h);
        }else if(k < arr[mid]){
                binsearch2(arr, k, l, mid - 1);
        }
        return -1;
}

二、今複雑な点の二分検索の問題を考えて、私達がこのような数に出会う時
グループa={1,2,3,3,5,7,8}は、重複する要素が存在し、そこから3が初めて現れる位置を見つける必要があります.ここで3が初めて現れる位置は2で、「プログラミング珠玉」ではよく分析されています.二分探索の主な精髄は不変式の設計(上のwhileサイクル条件式)です.

int binsearch_first(int arr[], int k, int n){
        int l = -1, h =  n;
        while(l + 1 != h){
                int m = (l + h) / 2;
                if(k > arr[m]){
                        l = m;
                }else{
                        h = m;
                }
        }
        int p = h;
        if(p >= n || arr[p] != k){
                return -1;
        }
        return h;
}

アルゴリズム解析:2つの存在しない要素a[−1]とa[n]を設定し、a[−1]l=−1,(l+u)/2a[l]&&t<=a[u]である.ループ終了時には必ずl+1=uがあり,a[l]uの値はtが現れる可能性のある位置であり、その範囲は[0,n]であり、tが配列にある場合、最初に現れる位置p=u、いない場合、p=-1が戻るように設定されている.このアルゴリズムの効率はより複雑な問題を解決したが,初期バージョンの二分検索よりも効率が高い.なぜなら,サイクルごとに1回しか比較する必要がなく,前のプログラムでは通常2回比較する必要があるからである.
例を挙げると、配列a={1,2,3,3,5,7,8}については、t=3を検索するとp=u=2が得られ、t=4を検索するとa[3]=n、例えばt=9である、u=7であり、この場合もp=-1が設定.
特に、l=−1、u=nの2つの値をl=0、u=n−1と書くことはできない.この2つの値はアクセスされませんが、後で変更すると、2点検索に失敗し、最初の数値にアクセスできません.a={1,2,3,4,5}で1を検索すると、初期にl=0,u=n-1を設定すると、検索に失敗します.
同じ理屈:配列内の要素が最後に現れる場所を検索するには、次のようにします.

int binsearch_last(int arr[], int k, int n){
        int l = -1, h =  n;
        while(l + 1 != h){
                int m = (l + h) / 2;
                if(k >= arr[m]){
                        l = m;
                }else{
                        h = m;
                }
        }
        int p = l;
        if(p <= -1 || arr[p] != k){
                return -1;
        }
        return p;
}

三、回転配列中の要素の検索
回転配列とは,回転配列とは,{4,5,1,2,3}が{1,2,3,4,5}の3を中心とした1つの秩序配列を1つの点を中心に回転(前後逆転)するものである.これで配列は全体的に無秩序になりますが、部分的に秩序化されています.
最初のソリューション:
回転する中点を見つけ、2つの部分的に秩序化された配列をそれぞれ二分的に検索できます.

int split(int a[], int n)
{
    for (int i=0; i<n-1; i++) {
        if (a[i+1] < a[i])
            return i;
    }
    return -1;
}

int bsearch_rotate(int a[], int n, int t)
{
    int p = split(a, n); //      
    if (p == -1)
        return bsearch_first(a, n, t); //       ，         
    else {
        int left = bsearch_first(a, p+1, t); //      
        if (left == -1) {  //        ，       
            int right = bsearch_first(a+p+1, n-p-1, t); //      
            if (right != -1) return right+p+1;  //    ，     p+1
            return -1;
        }
        return left; //      ，     
    }
}

もう一つの方法は、一度に二分検索する形で行うことであり、配列の中点を計算する際に、配列を二つの部分に分け、一部が秩序化されているか、あるいは二つの部分が秩序化されているかを考えることができます.つまり、必ず一度は秩序化されているので、二分の考え方で解くことができます.
二分探索アルゴリズムには2つのキーがある:1)配列秩序;2)現在の区間の中間要素とxの大きさの関係から,次の二分探索が前半区間か後半区間かを決定する.
この問題をよく分析すると,lowとhighからmidを求めるたびに,midの左側([low,mid])と右側([mid,high])の少なくとも1つが秩序化されていることが分かった.
a[mid]はそれぞれa[left]とa[right]と比較し,どのセグメントが秩序化されているかを決定する.
左側が整列している場合、xa[left]である場合、right=mid-1である.その他の場合、left=mid+1;
右側が整列している場合、x>a[mid]でxコードは次のとおりです.

int bsearch_rotate(int a[], int n, int t)
{
    int low = 0, high = n-1;
    while (low <= high) {
        int mid = low + (high-low) / 2;
        if (t == a[mid])
            return mid;
        if (a[mid] >= a[low]) { //      
            if (t >= a[low] && t < a[mid])
                high = mid - 1;
            else
                low = mid + 1;
        } else {       //       
            if (t > a[mid] && t <= a[high])
                low = mid + 1;
            else
                high = mid - 1;
        }   
    }   
    return -1; 
}

四、秩序配列の挿入問題
実は秩序配列の挿入問題も二分探索で実現できるが,戻り値が異なるだけで,要素が見つからないときにl(最左値)値を返すのが要素が挿入すべき位置である.

int binsearch1(int arr[], int k, int l, int h){
        if(l > h){
                return -1;
        }
        int mid;
        while(l <= h){
                mid = (l + h) / 2;
                if(k == arr[mid]){
                        return mid;
                }else if(k > arr[mid]){
                        l = mid + 1;
                }else{
                        h = mid - 1;
                }
        }
        return l;
}

五、二分思想の変形、実は二分は1種の思想で、秩序序列に応用するだけではなくて、多くの序列を区分する問題に応用することができて、例えば:
最大40億個のランダムに配列された32ビットの整数を含むシーケンスファイルを指定し、ファイルにない32ビットの整数を見つけます.
この問題は二分とはまったく関係ないように見えるが、二分の思想を利用して解決することができる.すべての要素をビットで2つの集合に分け、要素の個数の小さい集合を選択するたびにビットで2つの部分に分け、最後にファイルにない32桁の要素を見つけることだ.参考:二分検索のパズル
『プログラミング珠玉』

codility上の問題(14)Nu 2011

POJ 3264 RMQ問題STアルゴリズム