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