JavaScript - 二进制搜索每次都会挂起

Question

我有一个二维数组，如下所示:

[1.11, 23]
[2.22, 52]
[3.33, 61]
...

其中数组按每行中的第一个值排序。

我试图在数组中找到一个接近搜索值的值 - 在一定的敏感度内。设置方式和灵敏度值确保数组中只有一个可能的匹配项。

搜索值是鼠标当前的x-pos。搜索在 mousemove 上调用，因此经常被调用。

最初我有以下内容(使用从头到尾的 for 循环):

for(var i = 0; i < arr.length; i++){
    if(Math.abs(arr[i][0] - x) <= sensitivity){
        hit = true;
        break;
    }
}

它就像一个魅力。到目前为止，我只使用了小数据集，所以使用这种方法没有明显的延迟。但是，最终我将使用更大的数据集，因此想将其切换为二进制搜索:

var a = 0;
var b = arr.length - 1;
var c = 0;

while(a < b){
    c = Math.floor((a + b) / 2);

    if(Math.abs(arr[c][0] - x) <= sensitivity){
        hit = true;
        break;
    }else if(arr[c][0] < x){
        a = c;
    }else{
        b = c;
    }
}

这一切都很好，持续了 2 秒，然后它挂到我需要重新启动浏览器的地步。我过去经常使用二分搜索，但我终究无法弄清楚为什么这个搜索不能正常工作。

编辑 1

var sensitivity = (width / arr.length) / 2.001

数组中的点是等距的，因此这种敏感性确保在两个 arr 值之间没有模糊的 1/2 路点。你要么在其中一个。

值是在页面加载时动态创建的，但看起来与我上面提到的完全一样。 x值有更多有效数字，y值到处都是，但我提供的小样本和生成的小样本没有显着差异。

编辑 2

打印一个动态创建的列表:

[111.19999999999999, 358.8733333333333]
[131.4181818181818, 408.01333333333326]
[151.63636363636363, 249.25333333333327]
[171.85454545454544, 261.01333333333326]
[192.07272727272726, 298.39333333333326]
[212.29090909090908, 254.2933333333333]
[232.5090909090909, 308.47333333333324]
[252.72727272727272, 331.1533333333333]
[272.94545454545454, 386.1733333333333]
[293.16363636363633, 384.9133333333333]
[313.3818181818182, 224.05333333333328]
[333.6, 284.53333333333325]
[353.81818181818187, 278.2333333333333]
[374.0363636363637, 391.63333333333327]
[394.25454545454556, 322.33333333333326]
[414.4727272727274, 300.9133333333333]
[434.69090909090926, 452.95333333333326]
[454.9090909090911, 327.7933333333333]
[475.12727272727295, 394.9933333333332]
[495.3454545454548, 451.27333333333326]
[515.5636363636366, 350.89333333333326]
[535.7818181818185, 308.47333333333324]
[556.0000000000003, 395.83333333333326]
[576.2181818181822, 341.23333333333323]
[596.436363636364, 371.47333333333324]
[616.6545454545459, 436.9933333333333]
[636.8727272727277, 280.7533333333333]
[657.0909090909096, 395.4133333333333]
[677.3090909090914, 433.21333333333325]
[697.5272727272733, 355.09333333333325]
[717.7454545454551, 333.2533333333333]
[737.963636363637, 255.55333333333328]
[758.1818181818188, 204.7333333333333]
[778.4000000000007, 199.69333333333327]
[798.6181818181825, 202.63333333333327]
[818.8363636363644, 253.87333333333328]
[839.0545454545462, 410.5333333333333]
[859.272727272728, 345.85333333333324]
[879.4909090909099, 305.11333333333323]
[899.7090909090917, 337.8733333333333]
[919.9272727272736, 351.3133333333333]
[940.1454545454554, 324.01333333333326]
[960.3636363636373, 331.57333333333327]
[980.5818181818191, 447.4933333333333]
[1000.800000000001, 432.3733333333333]

如您所见，它按每行中的第一个值升序排列。

解决方案

将条件更改为

while(a < b)

和

var b = positions.length;

和

else if(arr[c][0] < x){
    a = c + 1;
}

成功了。

Answer 1

你的二分搜索似乎有点不对劲:试试这个。

var arr = [[1,0],[3,0],[5,0]];

var lo = 0;
var hi = arr.length;

var x = 5;
var sensitivity = 0.1;

while (lo < hi) {
    var c = Math.floor((lo + hi) / 2);
    if (Math.abs(arr[c][0] - x) <= sensitivity) {
        hit = true;
        console.log("FOUND " + c);
        break;
    } else if (x > arr[c][0]) {
        lo = c + 1;
    } else {
        hi = c;
    }
}

---

这是对任何实现二进制搜索的人的一般引用。

让:

• lo 是可能包含您的值的最小索引，
• hi 比可能包含您的值的最大索引多一个

如果遵循这些约定，那么二分查找就是:

while (lo < hi) {
    var mid = (lo + hi) / 2;

    if (query == ary[mid]) {
        // do stuff

    else if (query < ary[mid]) {

        // query is smaller than mid
        // so query can be anywhere between lo and (mid - 1)
        // the upper bound should be adjusted

        hi = mid;
     else {

        // query can be anywhere between (mid + 1) and hi.
        // adjust the lower bound

        lo = mid + 1;
}