有效二值搜索

Question

我的实施：

Array.prototype.binarySearchFast = function(search) {

  var size = this.length,
      high = size -1,
      low = 0;

  while (high > low) {

    if (this[low] === search) return low;
    else if (this[high] === search) return high;

    target = (((search - this[low]) / (this[high] - this[low])) * (high - low)) >>> 0;

    if (this[target] === search) return target;
    else if (search > this[target]) low = target + 1, high--;
    else high = target - 1, low++;
  }

  return -1;
};

正常执行：

Array.prototype.binarySearch = function(find) {
  var low = 0, high = this.length - 1,
      i, comparison;
  while (low <= high) {
    i = Math.floor((low + high) / 2);
    if (this[i] < find) { low = i + 1; continue; };
    if (this[i] > find) { high = i - 1; continue; };
    return i;
  }
  return null;
};

不同的是，我的实现是根据起始位置和结束位置的值来猜测值的索引，而不是每次直接到中间值。

我想知道是否有人能想到比原来的实现慢一些的情况。

更新:很抱歉出现了坏的例子。现在，我已经使它们更容易理解，并在jsPerf上设置了一些测试。见这里：

http://jsperf.com/binary-search-2

用我的方法，我看到了大约75%的进步。

Answer 1

我的建议是，不要乱搞一些经过良好和真正检验的东西:-)

不，不完全是:如果你找到了一个比它更好的算法，那就一定要使用它。然而，在这种情况下，对于一般数据来说，这并不是一个改进。

二进制搜索和其他O(log N)类型算法的强大之处在于，在每次迭代时，您会将剩余搜索空间的一半处理掉。换句话说，如果初始搜索空间(数组大小)为1000，则第一次迭代将删除其中的500个。

在迭代过程中，对“中点”(在搜索空间中保留的内容与正在处理的内容之间的分隔符)的任何更改都有可能提高或降低性能。例如，将中点设置为25%可能会更快地减少搜索空间(如果您是对的)或更慢(如果您错了)。

现在，如果您知道数据的某些属性，您可以利用它来改进算法。事实上，正是关于列表的“额外”知识(排序的事实)允许您优化通常是顺序搜索到二进制搜索的内容。

所以这一切都取决于你的额外信息有多好。在这种情况下，仅两个端节点的值并不能真正表示中点应该在哪里。你只需看一看清单：

[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 500, 1000]

看到这一切付诸行动。

如果您在该列表中寻找500，您可能会根据第一个和最后一个元素1和1000，决定它将位于中间位置，这显然不是这样的。

类似地，如果您正在寻找14，您可能首先在1.4%的标记(14/1000)附近检查元素，这可能是第一个元素，尽管它就在另一端。

当然，这并不是说其他额外的信息不会有帮助。如果您知道数据在范围内分布相当均匀，那么您的改进可能是值得的。

您还需要意识到，通常只有在大量的数据输入时才会很重要，所以即使结果更好，也不一定值得。对于100个元素，即使气泡排序速度也是惊人的:-)

Answer 2

看看这个http://en.wikipedia.org/wiki/Interpolation_搜索

特别是其中一段规定：

上述代码的每一次迭代都需要五到六次比较(额外的原因是在没有三次比较的情况下，通过二进制比较来区分<>和=的三种状态所需的重复)加上一些杂乱无章的算法，而二进制搜索算法可以用每次迭代编写一次比较，并且只使用平凡的整数算法。因此，它将搜索一个由一百万个元素组成的数组，不超过20个比较(涉及访问存储数组元素的缓慢内存)；*击败上面所写的插值搜索不允许超过三次迭代。*

Answer 3

我想我应该对它们进行测试，但是我注意到这两个实现都没有参数，所以它们不知道要查找什么.

无论如何，当数组中没有均匀分布时，“快速”实现就会更慢。例如，在5中查找[1,2,3,4,5,6,7,10000]会产生类似于四个迭代而不是一个迭代的结果。