バイナリ検索(TIL 56日)

「半分半分」
シーヶンスサーチ
シーケンスナビゲーションは、名前に示すように、前から順にデータをチェックする方法です.配列で、目的の値を検索する場合は、繰り返し文を使用して最初から最後まで値をナビゲートして比較できます.これがシーケンスナビゲーションです.
シーケンスナビゲーションの利点は、アレイ内のデータが整列していなくても、所望の結果が得られることである.実施は非常に簡単で簡単です.しかし欠点は,配列中のすべての要素を確認するために時間がかかることである.最悪の場合,シーケンシャルナビゲーションの時間的複雑度はO(N)である.
バイナリサーチ
バイナリナビゲーションはシーケンスナビゲーションの欠点を補うことができる.バイナリ検索とは、データを半分に分けて、検索したい値がある部分だけを再検索することです.デジタルゲームの方がわかりやすいと思います
1~100の数字の中で、相手に心の中で1つの数字を考えさせた後、up&downでゆっくり範囲を絞って数字を当てるゲームをしたことがありますか?幸いなことに、一度に1つの数字を合わせることができますが、問題を解決する最も合理的な方法は中間値を見つけて、範囲を半分に縮小することです.
バイナリ・ナビゲーションは、データを中間値に切断し、検索する値のある部分だけを取り外してナビゲーションを続行します.シーケンスナビゲーションと比較して,時間的複雑さはO(log 2 N)であり,データ全体を遍歴する必要がなく,不要な部分を半分ずつ削除するためである.すぐに欲しい値が見つかります.
逆に、バイナリナビゲーションは、データをソートしなければ使用できないアルゴリズムです.データがランダムである場合、データをどのくらいの半分に分けても、検索する値がどこにあるかはわかりません.したがって、バイナリ・ナビゲーションを使用するには、必要な結果を得るために、データがソートされているかどうかを判断する必要があります.
バイナリナビゲーションの応用
毎日午前9時から1時間にかけてToyProblemという時間があります.今日の問題は、部分的な昇順配列で検索する値を検索し、その位置を返す方法です.
ここで、ローカル配列とは、データを左または右に1つのセルを移動し、最後のデータを反対側に移動して配列し、ある時点で完全に整列させることです.たとえば、[1,2,0]と同じ配列がある場合、データをセルに右に移動すると、0が先頭の[0,1,2]の形式になり、配列がソートされるため、前述の条件に合致します.小さい値から大きい値を基準としてリストされるので、昇順に並べられています.
部分的な位置合わせのため、バイナリナビゲーションは依然として使用できます.でも直接使うことはできません少し変形してから使うことができます既存のバイナリ・ナビゲーションで範囲を縮小でき、検索する数値をターゲットと比較するだけで、この場合、範囲を複数の条件に縮小する必要がある場合があります.
最初の条件
バイナリナビゲーションでは、まず中間値を指定してください.中間値が検索する値である場合は、すぐに位置に戻るだけで、さらにナビゲートする必要はありません.この状況はそのまま終わればいいのですただし、そうしないと、指定された配列は部分的に整列するだけなので、中間値だけではどこでナビゲートするか分かりません.
配列の0番目の値を指定した中間値と比較するとどうなりますか?少なくともそうすれば,中間値に基づいてどちらが整列したアレイであるかを決定できる.中間値が0より大きい場合は、少なくとも0から中間までの配列が昇順に配列されていることを示します.逆に、中間値が0より小さい場合、中間から最後までの値は昇順に並べられます.
文字で説明するだけではわかりにくいので、一例を見てみましょう.

let a = [5, 6, 0, 1, 2, 3, 4]

let b = [2, 3, 4, 5, 6, 0, 1]

aの左3要素、右3要素は、1に対して.b 5を基準として、同様に左側に3つの要素があり、右側に3つの要素がある.
0番目の要素5(aから1)に比べて、1番目の要素5は5未満であるため、右側の部分は中間値に対して昇順に並んでいることがわかります.
逆に、bでは5が中間値であり、0番目の要素が2であるため、中間値が0番目の要素より小さいため、左側は昇順に並べられている.
これにより、少なくとも1つのアレイが昇順に配列されていることを確認することができる.
2番目の条件
最初の条件だけでは、私たちが探している値がどこにあるか分からないので、2番目の条件を追加する必要があります.2番目の条件は1番目の条件を基準に決めます
まず,左側が中間値に対して配列された配列,すなわち1である.アレイの0番目の要素が中間値より小さい場合.
左側の配列は整列した配列であるため,我々が探している値targetが1未満)の中間値,2)が0番目の要素より大きい場合を基準とすることができる.まず、二つの条件が~であれば、また~であれば、言い換えれば&&条件であれば、まず理解し、例とともに補足説明を行います.

let b = [2, 3, 4, 5, 6, 0, 1]

let target = 4

例えば、上にbという配列があり、4を検索する必要がある場合、4は1を表し、中間値(==5)より小さく、2は0番目の要素(==2)より大きい.条件この場合、左側の配列に左揃えが表示されるため、左側の配列で必要な値にナビゲートできます.
targetが0だったらどうなるの?0は、中間値5より小さいため、条件1を満たす.0番目の要素2より小さいため、条件2を満たさない.この場合、右側の配列が整列していない場合でも、右側をチェックする必要があります.
実際、targetが0番目の要素より小さい場合、最初の条件は当然中間値より小さくなります.targetが中間値より大きい場合、同じように0番目の要素より大きくなります.両方の条件がfalse(中間値より大きく、0番目の要素より小さい)の場合、最初から成立することはできません.したがって、この場合、右側をすべてチェックできます.
もし私たちがそれをしたら、私たちは反対の状況でも、私たちの方法に大きな違いはないことに気づきます.0番目の要素は、中間値より大きい場合があります.この場合、右側の配列は、上図のように整列した配列である.検索する値が1)の中間値より大きく、2)が最後の要素より小さい場合は、2番目の条件です.これに満足すると、検索する値は右側のソートされた配列にある必要があると推測できます.

let a = [5, 6, 0, 1, 2, 3, 4]
let target = 5

上記の配列が例である場合、前述と同様に、中間値未満の場合、当然0番目の要素よりも小さい.逆に、最後の要素より大きい場合は、自然に中間値より大きいです.どちらもfalseの場合は成立しないことも理解できる.
アプリケーションでは実際の問題が関連しているため、すべてのコードを記述する必要はありません.解法をより詳細に書きます.リファレンスコードの内容は口頭のデジタルコードと見なしてもよいので、リファレンスコードを理解していない場合は、役に立つことを望んでいます.