JavaScriptのバイナリ検索。 実用例

バイナリ検索とは何ですか？

配列を検索する必要がある場合、最も簡単な方法はindexOf（）ループ、または場合によってはfor（）ループを使用することです。 これらのメソッドはいずれも、配列の先頭から繰り返し処理を開始し、目的の値が見つかるまで配列の各要素を調べます。



次に、これをバイナリ検索と比較します 。



バイナリ検索では、配列を半分に繰り返し分割することにより、ソートされた配列を検索できます。



バイナリ検索は、検索値が配列の平均値よりも大きいか、 小さいか、 等しいかどうかをチェックすることで実行されます。

• 小さい場合は、配列の右半分を削除できます。
• 大きい場合は、配列の左半分を削除できます。
• 等しい場合、値を返します

しかし、一番下の行は、配列を並べ替える必要があるということです。つまり、バイナリ検索が正しく機能するためには、値が正しい順序でなければなりません。



大量のデータを処理する場合、反復ごとに不適切な値が1つだけでなく、不要な配列値の半分が削除されるため、バイナリ検索を使用する方がはるかに効率的です。

プロジェクト

私は最近、React APIから30日間のインタラクティブなビットコイン価格チャートを作成した方法に関する記事を投稿しました。



チャートの最も重要な側面の1つは、チャートにカーソルを合わせると関連データを表示するツールチップです。 ツールチップ上でマウスを動かすと、チャートの最も近いポイントからのデータが更新されます。 例：







どのように機能しますか？



すべての座標と対応するデータの配列があります。 座標はオブジェクト内にあり、各オブジェクトにはsvgXキーがあります。 次のようになります。

svgData = [ {svgX: 1367.844, data...}, {svgX: 1684.478, data...}, {svgX: 1168.474, data...}, {svgX: 1344.854, data...}, // etc. ]
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

最初に、単純なforループを使用して、マウスカーソルの現在のX座標をデータ配列内のすべてのsvgX値と比較しました。

サイクル

forループコードは次のようになります。 すべてのsvgX値を反復処理し、マウスカーソルのX座標に近い値​​を持つオブジェクトは、データを表示するオブジェクトです。

 const {svgWidth} = this.props; let closestPoint = {}; for(let i = 0, c = svgWidth; i < svgData.length; i++){ if ( Math.abs(svgData[i].svgX — this.state.hoverLoc) <= c ){ c = Math.abs(svgData[i].svgX — this.state.hoverLoc); closestPoint = svgData[i]; } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

まず、svg要素の幅を取得し、空のオブジェクトを作成して、最も近いポイントを保存します。

 const {svgWidth} = this.props; let closestPoint = {};
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

次に、データ配列を反復処理します。 配列内のオブジェクトの各svgX値は、マウスカーソルのX座標と比較されます。 ループの現在の反復が他の反復よりもカーソルに近い値を持つ場合、このポイントは最も近いポイントとして設定されます。



データ量が少ない場合、この方法は比較的高速です。 ただし、大量のデータがある場合、このオプションは効果的ではなくなります。

バイナリ検索

以下は、最も近い値を見つけるためのバイナリ検索コードの例です。

 const binarySearch = (data, target, start, end) => { if(end < 1) return data[0]; const middle = Math.floor((start + (end - start)/2); if (target == data[middle].svgX) return data[middle]; if (end — 1 === start) return Math.abs(data[start].svgX — target) > Math.abs(data[end].svgX — target) ? data[end] : data[start]; if (target > data[middle].svgX) return binarySearch(data,target,middle,end); if (target < data[middle].svgX) return binarySearch(data,target,start,middle); } let closestPoint = binarySearch(data,target, 0, data.length-1)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

バイナリ検索には5つの主要なコンポーネントが必要です。

1. データ- データ。 オブジェクトの配列。
2. ターゲットはターゲットです。 マウスカーソルの位置（x座標）。
3. startは始まりです。 バイナリ検索の現在の反復の配列内の開始位置。
4. end- 終わり。 バイナリ検索の現在の反復の配列内の終了位置。
5. 真ん中です。 バイナリ検索の現在の反復の配列の中央。

これは少しわかりにくいので、上のコードを単純化する例を見てみましょう。 この例では、目標値は3.7です。 1から5までの5つの増加する数字の配列を検索します。



10行目の上記のコードからわかるように、バイナリ検索を開始するときに、データ配列全体、マウスオブジェクト、配列のフルサイズに等しい開始位置0および終了位置を入力に渡します。



データが得られたら、開始位置と終了位置の合計を2で割ることにより、配列の中央を見つけます。 分数を取得しないために、結果の数値は切り捨てられます。

 const middle = Math.floor((start + (end - start)/2);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

したがって、mid 0 +（4-0）/ 2は切り捨て= 2です。



この例では、目標値が3.7であることを覚えています。 中間の位置を見つけたら、目標値と等しいかどうかを確認します。 その場合、オブジェクトを返し、完了です！

 if (target == data[middle].svgX) return data[middle];
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

残念ながら、配列の平均値は3です。そして、目標は3.7です。



次に、最終位置-1が初期位置と一致するかどうかを確認します。

 if (end — 1 === start) { return Math.abs(data[start].svgX — target) > Math.abs(data[end].svgX — target) ? data[end] : data[start]; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

この条件は、配列が2つの最終値に削減され、目標がそれらの間にある場合に機能します。 この場合、近い値を返します。



現在の反復では、条件はfalseを返します。



次に、目標値が平均よりも大きいかどうかを確認します。

 if (target > data[middle].svgX) return binarySearch(data,target,middle,end);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これが私たちのケースです！ 3.7の目標値は、平均3よりも大きくなっています。配列の最初の2つの値を取り除くことができます。





再帰を使用して、binarySearch（）関数の新しい呼び出しを返します。 配列を関数に渡します。ターゲット値は3.7で、 平均値を初期位置として、最終値を最終位置として使用します。



binarySearch（）の新しい呼び出しは、位置2からdata.length-1まで検索します。





関数は新しい中間位置データを見つけます[3]：



3.7のターゲット値は4の平均値よりも小さいため、配列の右側を破棄し、binarySearch（）関数の新しい呼び出しを返します。 今回は初期位置はデータのままであり[2]、最終位置は平均データに変わります[3]。



条件が満たされる瞬間に到達しました：

 if (end — 1 === start) { return Math.abs(data[start].svgX — target) > Math.abs(data[end].svgX — target) ? data[end] : data[start]; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

最終値から1を引いた値が初期値に等しいため、目標値が中間にあることがわかります。 値が3.7の値に近い配列の要素を返す必要があります。 4 （最終値）が近いため、それぞれ対応する要素を返します：data [3]。

速度試験

データの量が少ない場合、再帰はforループよりも遅くなる可能性があります。 10個の要素を持つjsperfでテストする場合、再帰関数はforループよりも平均で3％遅くなります。 ただし、10,000要素では、forループは再帰関数よりも72％遅くなります。 これは、再帰がforループのほぼ2倍の速度であり、時間を大幅に節約できることを意味します。



JavaScriptのバイナリ検索の基本を理解したことを願っています！