javascriptでバイナリサーチ(2分探索)を実装

スポンサーリンク
Pocket
LINEで送る

配列から特定の値を検索したい時に使う、サーチアルゴリズムについてです。

要素数が少ない配列からの検索は単純なのでリニアサーチ(線形探索)を使ったりしますが、要素数が多くなると処理が遅くなってしまうので高速に処理したい時はバイナリサーチ(2分探索)を使います。

ちなみに2分探索は数値が大小の順番に並んでいる必要があります。

 

javascriptでバイナリサーチ

実際にコードを書いてみます。

function binarySearch(){
  var targets = [1,2,3,4,5,6,7,8,9,10]; 
  var left = 0;
  var right = targets.length;
  var key = 6;

  while(left < right){
    mid = (left + right) / 2;
    mid = Math.floor(mid);
  if(targets[mid] == key){
    return mid;
  }else if(key < targets[mid]){
    right = mid;
  }else{
    left = mid + 1;
  }
 }
 return "not found";
}
console.dir(binarySearch());

 

こんな感じです。

アルゴリズムの解説

1:要素数を半分に割り中央のキーを取得

2:マッチしたら返す

3:中央の値より検索したい値より大きかったら右を探索範囲にする。小さかったら左を探索範囲にする。

スポンサーリンク

これを繰りかえして目的の値を探索します。