javascript - ソートされた配列に存在する一連の整数の中からすべてを見つける

Question

重複の可能性:
JavaScript での配列交差の最も単純なコード

JavaScriptでソートされた整数の配列があります。その並べ替えられた配列に存在する整数の束の中からどれが存在するかを調べる必要があります。それを行うための最速の方法は何ですか？

私はjQueryを使用していますが、ソートされた配列のバイナリ検索の組み込みサポートを提供していないようですが、jQuery.inArray()実装されているアルゴリズムがわからないだけです。

Answer 1

JavaScript 言語も jQuery もバイナリ検索機能を提供しません。

次のようになります。

function binarySearch(array, val, cmp) {
  cmp = cmp || function(v1, v2) { return v1 - v2; };
  var l = 0, h = array.length - 1;
  while (l <= h) {
    var m = Math.round((l + h) / 2), diff = cmp(array[m], val);
    if (!diff) {
      return m;
    }
    diff > 0 ? (h = m - 1) : (l = m + 1);
  }

  return -1;
}

binarySearch([1, 10, 100, 1000], 666); // -1