JavaScript的 - 二进制搜索挂起每次 [英] JavaScript - Binary search hangs every time

问题描述

我有一个二维数组，类似如下：

I have a 2D array, something like the following:

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

凡阵列由每行中的第一个值排序。

Where the array is ordered by the first value in each row.

我想的数组，它是关闭应用于搜索值范围内找到的值 - 在一定的敏感性内。这是设置方式，灵敏度的价值，确保在阵列中只有一个可能的匹配。

I am trying to find a value within the array that is close to the search value - within a certain sensitivity. The way this is set up, and the value of the sensitivity, ensure only one possible match within the array.

搜索值是鼠标当前的X-POS。搜索是呼吁鼠标移动，因此是被称为频繁。

The search value is the current x-pos of the mouse. The search is called on mousemove, and so is being called often.

我本来以下（使用开始到结束为循环）：

Originally I had the following (using a start-to-end for loop):

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

和它的工作原理就像一个魅力。到目前为止，我只使用小数据集去过，所以使用这种方法没有明显的滞后性。但是，最终我将使用更大的数据集，所以想将这个切换到的二进制搜索的：

And it works like a charm. So far, I've only been using small data sets, so there is no apparent lag using this method. But, eventually I will be using much larger data sets, and so want to switch this to a Binary Search:

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秒，然后将其挂到我需要重新启动我的浏览器的地步。我使用二进制搜索大量的过去，并不能为我的生命弄清楚为什么这个人是不正常。

This works well, for all of 2 seconds, and then it hangs to the point where I need to restart my browser. I've used binary searches plenty in the past, and cannot for the life of me figure out why this one isn't working properly.

修改1

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

在阵列中的点是等距离的，所以这种敏感性确保有两个之间没有任何暧昧的1月2日的点位ARR 值。你不是在一个或其他。

The points in the array are equidistant, and so this sensitivity ensures that there is no ambiguous 1/2-way point in between two arr values. You are either in one or the other.

数值在页面加载动态创建的，但看起来完全像什么我上面提到的。 x值具有更显著的数字，并且y的值是所有的地方，但有我所提供的小样品和所生成的一个之间没有显著差异。

Values are created dynamically at page load, but look exactly like what I've mentioned above. The x-values have more significant figures, and the y values are all over the place, but there is no significant difference between the small sample I provided and the generated one.

编辑2

印刷这是动态创建一个列表：

Printed a list that was dynamically created:

[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]

正如你所看到的，它是由每一行的第一个值排序，升。

As you can see, it is ordered by the first value in each row, ascending.

SOLUTION

更改条件

while(a < b)

和

var b = positions.length;

和

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

做的伎俩。

推荐答案

您的二进制搜索似乎是有点过。试试这个

Your binary search seems to be a bit off: try this.

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;
    }
}

---

这意味着作为一般的参考实现二进制搜索任何人。

---

This is meant as a general reference to anyone implementing binary search.

让：

• 罗是可能含有你的价值最小的指数，


• 喜是多了一个的比可能包含你的价值最大的指数

• lo be the smallest index that may possibly contain your value,
• hi be one more than the largest index that may contain your value

如果这些规则得到遵守，那么二进制搜索很简单：

If these conventions are followed, then binary search is simply:

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;
}

这篇关于JavaScript的 - 二进制搜索挂起每次的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！