二分検索実装の詳細

6313 ワード

にぶんたんさく

第1部

原理は、ある数がその中にあるかどうかを決定するなど、秩序配列に関連する問題であり、二分ルックアップを用いてlog(n)の複雑さを達成することができる.

の原理は簡単であるが、実際に符号化を実現するには、バグがないのは容易ではないことが多い.私は何度も実践したことがあります.書き終わるたびに何度もデバッグしてこそ、多くのバグを取り除くことができます.しかし、面接の过程で、面接官はあなたが普段コードが多くないことを见て、きっとあなたにそんなに多くの机会をデバッグさせないで、あなたはせいぜい心の中でデバッグすることができて、このように往々にして多くのバグを残して、走ると间违いがあるかもしれません.

以下は、バグが最も多く発生した理由のまとめ(start、mid、endはそれぞれヘッダ、中点、末尾のカーソルまたはポインタを表す)

whileサイクルでデッドサイクルが発生したのは、midがstartを更新し、(start

最終戻り値カーソルはmidを採用し、結果エラーを引き起こした.

原因と解決方法

対1は、最後にstart=end-1、すなわち両者が隣接する場合があるため、mid=(start+end)/2であり、intではmid=startの後、if文でstart=midという更新カーソル文が現れると、自然とデッドサイクルに陥る.したがって、前のカーソルが直接midによって更新されることを回避します.すなわち、start=mid+1を使用します.この場合、end更新に等しい場合を移動して完了します.end=midです.この場合、デッドサイクルは発生しません.

対2は、最後のstart=end後にwhileループから飛び出すため、この条件が成立するのは、start=mid+1、すなわち、最終値は更新後の(start+end)/2であるべきであり、ループから飛び出すため、更新後の値は得られず、前のステップのmid値である.したがって、最終的な出力カーソルはendを採用することができ、startも可能であるはずです.e.g.以下、昇順配列arrにおいて、start=mid+1がデッドサイクルを出現させないvalueが存在するか否かを調べる例である.

    public boolean ascendingFind(int[] arr, int start, int end, int value){
        if (start > end) {
            return false;
         }
        int mid = 0;
        while(start < end){
        mid = (start + end) >> 1;
        if(arr[mid] < value){
            start = mid + 1;
        }else{
            end = mid;
          }
        }
        if (arr[end] == value) {
            return true;
        }
        return false;
    }

第2部

典型的なアプリケーションシーンプログラム分析

上記のまとめを経て、手応えがあると思っていたが、緊張状態でも論理分析が混乱していることが分かった.唯一のメリットは、バグを引き起こす可能性が高い点がstartの上にあること、隣接するstartとendの分析があることだ.

  1.  a[]（ ）,  m， m a /

一番左の位置は、a[mid]m、end=mid-1を使わずにこのように選んだのでしょうか.第1部の原理によれば,最後にstartとmidが交互に付与されるデッドサイクルの問題を避けるために,startを更新する際にstart=midを用いないようにしたい.しかし、start=midのような状況を避けることができない場合もあり、別途考慮する必要があります.これで私たちは

    //  m , m a ， m 
    public int leftMostEqual(int[] a, int m){
        int start = 0;
        int end = a.length - 1;
        int mid;
        while(start < end){
            mid = start + (end - start) / 2;
            if (a[mid] < m) {
                start = mid + 1;
            }else {
                end = mid;
            }
        }
        return end;

では、最後の戻り値はstart、end、midを取りますか?解析ではstart=end,midはまだ更新されていない可能性があるのでendを選択すべきである.また、mがaにない場合、上のコード出力はmの最初の下付き文字より大きい.ここでは次の質問に対応しています.
int[]aの中でm以上の一番左の下の記号を見つけます
の解は、実装上は完全に同じで、インタフェースは:

public int leftMostGreatEqual(int[] a, int m)

次の質問は、aの中でmの一番右の位置を見つけて、上記の問題との違いは、start=mid+1はここでは使えません.a[start]=mの場合、現在のstartが最後の位置なのか、最初の位置なのか分からないので、右に移動することはできません.start=midしか使えません.このように、デッドサイクルを避けるために、while(start

 // m , m a ， m 
public int rightMostEqual(int[] a, int m){
int start = 0;
int end = a.length - 1;
int mid;
while(start < end - 1){
mid = start + (end - start) / 2;
if (a[mid] > m) {
end = mid - 1;
}else {
start = mid;
}
}
if(a[end] == m)
return end;
else {
return start;
}
}

終了条件をstartまた,ある与えられた数以下の右端の下付き文字を返す問題も,この問題解法と全く同じであり,彼らの本質は同じである.
このようにして、皆さんの質問と意見を歓迎します.

[Front-end🦁] #8 Webプロジェクト—Jungle Cinema/CSSアニメーション

Javascript_30_24