JavaScriptアルゴリズム:バイナリ検索

バイナリ検索は、検索している配列(またはその他のデータ構造)が順序付けられていることを前提としています。

配列と、検索する必要のあるアイテムから始めます。

配列の中央を見てみましょう。要素の数を取得し、それを2で割ります。左側に配列の一部があり、右側に他の部分があるとします。

私たちが持っているアイテムが私たちが探しているものよりも低い場合、それは正しい部分にある必要があります。そうすれば、右側の部分を完全に破棄できます。

次に、同じアクションを実行して、配列の右側の部分を2に分割し、中央の項目を見て、配列の一部を破棄します。

最後に、あなたはアイテムを手に入れます(またはあなたは戻りますnullアイテムが見つからない場合)。

最終的に、配列に8つのアイテムがある場合、最大4つのステップでアイテムが見つかります。

配列に32個のアイテムがある場合、最悪の場合、最大6つのステップがあります。線形検索の32と比較すると、これは非常に最適化されています。

二分探索にはO(log n) 複雑

これが可能な実装です:

const binarySearch = (list, item) => {
  let low = 0
  let high = list.length - 1

while (low <= high) { const mid = Math.floor((low + high) / 2) const guess = list[mid]

<span style="color:#66d9ef">if</span> (<span style="color:#a6e22e">guess</span> <span style="color:#f92672">===</span> <span style="color:#a6e22e">item</span>) {
  <span style="color:#66d9ef">return</span> <span style="color:#a6e22e">mid</span>
}

<span style="color:#66d9ef">if</span> (<span style="color:#a6e22e">guess</span> <span style="color:#f92672">&gt;</span> <span style="color:#a6e22e">item</span>) {
  <span style="color:#a6e22e">high</span> <span style="color:#f92672">=</span> <span style="color:#a6e22e">mid</span> <span style="color:#f92672">-</span> <span style="color:#ae81ff">1</span>
} <span style="color:#66d9ef">else</span> {
  <span style="color:#a6e22e">low</span> <span style="color:#f92672">=</span> <span style="color:#a6e22e">mid</span> <span style="color:#f92672">+</span> <span style="color:#ae81ff">1</span>
}

}

return null //if not found }

これはどのように作動しますか?私たちはlist配列、および探しているアイテムの値。次に、を初期化しますlow最初は0の値で、highリストの最後のインデックスへの値。最初に真ん中のアイテムを見て、それが私たちが探しているものである場合は、それを返し、完了です。そうでない場合は、lowまたはhigh配列の左側または右側の部分のみを確認する値を指定し、アイテムが見つかるまでこのプロセスを繰り返します。

配列内のアイテムのインデックスを返します。

console.log(binarySearch([1, 2, 3, 4, 5], 1)) //0
console.log(binarySearch([1, 2, 3, 4, 5], 5)) //4

我々は返しますnull要素が見つからない場合:

console.log(binarySearch([1, 2, 3, 4, 5], 6)) //null

私の無料ダウンロードJavaScriptビギナーズハンドブック


その他のjsチュートリアル: