JavaScript二进制搜索

我在早期用JavaScript编写了二进制搜索的实现，但是我发现我的版本与Google上的版本有很大不同。这是我在Google上发现的二进制搜索示例（已在此处复制以对抗链接腐烂）：但是在我的游戏中，我不会从低/高中减去一个并从那里继续。取而代之的是，我将数组一分为二，然后继续将适当的一面一分为二，直到达到正确的值为止。代码：

Array.prototype.binarySearch = function(find, comparator) {
    var low = 0, high = this.length - 1,
        i, comparison;

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

我也写了这种递归样式，但是在测试中我发现这个迭代版本更快。，我发现我在Google上找到的示例（尽管它们没有包括上面的示例，但它们几乎是相同的）在较小的数组上速度更快，但是随着输入量的增加，我的示例会超过这些示例。由于二进制搜索通常限制（？）到较大的输入大小，因此我认为这是一种改进。

我的想法正确吗？能否以更好的方式完成？

我也不喜欢这样：

function binary_search_iterative(arr, ele) {
    var beginning = 0, end = arr.length,
        target;
    while (true) {
        target = Math.floor((beginning + end) / 2);
        if ((target === end || target === beginning) && arr[target] !== ele) {
            return -1;
        }
        if (arr[target] > ele) {
            end = target;
        } else if (arr[target] < ele) {
            beginning = target;
        } else {
            return target;
        }
    }
}

我很好奇是否有消除它或在哪里重构函数的好方法。一般来说比较干净。

#1 楼

我只想强调一下两者之间的几点区别，以及我认为它们在您所看到的内容中所体现出的差异。如果它们不相同，则无需在下一次迭代的范围内包括arr[target]（因此+/- 1）。这可以减少比较的次数，尽管在较小的数据集上效果更明显。

遵循上述观点，当ele变为“找不到”时，终止就足够了，而不是检查您所查看的起始或结束值。同样，在以下情况下寻找“ B”时，您的方法可能会提供假否定的结果。

    target
    |
    v
... A B
    ^ ^
    | |
    | end
    beginning

在这种情况下，因为target ===开头和arr [target ]！== B，它返回-1。

谷歌代码使用target，我不确定这如何影响正确性，但我怀疑这会对性能产生不利影响。

我认为您在可伸缩性中看到的是因为Google代码没有进行比较，但是beginning > end使比较更加昂贵。对于较小的数据集，比较数量的减少更为显着，但是对于较大的数据集，比较的成本变得更加重要。 />

#2 楼

将Math.floor((beginning + end) / 2)更改为((beginning + end) >> 1)意味着同样的事情，并且更快：

http://jsperf.com/code-review-1480

\ $ \ begingroup \ $
+1我通常反对JS中的按位运算，但这很酷。它可以容纳更大的阵列！
\ $ \ endgroup \ $
–比尔·巴里
2012年6月16日的1:23

#3 楼

老实说，我从来都不是while（true）的粉丝。在我看来，最好将主要条件放在此处以提高可读性和样式。这是我写过一段时间的踢球版本，如果有帮助的话-我的目标主要是在推文中添加它-但在此示例中我对其进行了美化。注意，我使用的是Math.floor而不是parseInt-我的测试表明，当存在.5时，Math.floor的速度大约是它的两倍，而对整数进行处理时，它的速度只有一点点。此版本可能看起来很奇怪（找到匹配项时将三进制上限分配给-2），但这又是一次字节剃削实验。

#4 楼

除了使用parseInt之外，不同方法之间的性能差异很可能主要取决于Javascript实现。

使用积极的优化器（例如，在JIT编译器中），不同版本的效果可能几乎相同。对于其他人来说，这将是彩票。
对于任何给定的Javascript平台，很难预测哪个版本的代码将表现最佳。如果确实很重要，（我怀疑不会），则需要在您关注的所有Javascript平台上对方法的不同版本进行基准测试。

#5 楼

您的代码不会像Brian所建议的那样产生误报。 'end'总是指向一个被认为大于要找到的值的元素（将其作为逻辑元素经过数组）。然而。例如。如果数组的长度为零，则将取消引用arr [0]。在javascript中，这可能是可以接受的，但是对于C程序员来说，这看起来很奇怪。您的代码按行执行比较。为了正确比较这两种方法，您应该使用内联比较将代码与Google代码竞争。

编程黑洞网