JavaScript - 二进制搜索每次都挂起
JavaScript - Binary search hangs every time
我有一个二维数组，如下所示：
[1.11, 23]
[2.22, 52]
[3.33, 61]
...
其中数组按每行中的第一个值排序。
我试图在数组中找到一个与搜索值 接近 的值 - 在一定的灵敏度范围内。设置方式和灵敏度值确保数组中只有一个可能的匹配项。
搜索值为鼠标当前的x坐标。搜索是在 mousemove 上调用的，因此经常被调用。
最初我有以下内容（使用从头到尾的 for 循环）：
for(var i = 0; i < arr.length; i++){
if(Math.abs(arr[i][0] - x) <= sensitivity){
hit = true;
break;
}
}
它就像一个魅力。到目前为止，我只使用了小数据集，所以使用这种方法没有明显的延迟。但是，最终我将使用更大的数据集，因此想将其切换为 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 秒，然后它挂到我需要重新启动浏览器的地步。我过去经常使用二进制搜索，但我终究无法弄清楚为什么这个不能正常工作。
编辑 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;
}
成功了。
您的二分搜索似乎有点不对：试试这个。
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;
}
我不知道你的确切情况，但代码可能会崩溃：
1) 从具有两个 X 值的数组开始。这个数组的长度为 2，所以 a = 0, b = 1, c = 0.
2) a < b, while循环执行。
3) c = floor((a + b) / 2) = floor(0.5) = 0.
4) 假设鼠标不在第一个 X 值的灵敏度范围内，所以第一个 if 分支没有命中。
5) 假设我们的X值在我们鼠标的右边，所以第二个if分支进入。这将设置 a = c，或 0，它已经是。
6) 因此，我们得到一个死循环。
我有一个二维数组，如下所示：
[1.11, 23]
[2.22, 52]
[3.33, 61]
...
其中数组按每行中的第一个值排序。
我试图在数组中找到一个与搜索值 接近 的值 - 在一定的灵敏度范围内。设置方式和灵敏度值确保数组中只有一个可能的匹配项。
搜索值为鼠标当前的x坐标。搜索是在 mousemove 上调用的，因此经常被调用。
最初我有以下内容（使用从头到尾的 for 循环）：
for(var i = 0; i < arr.length; i++){
if(Math.abs(arr[i][0] - x) <= sensitivity){
hit = true;
break;
}
}
它就像一个魅力。到目前为止，我只使用了小数据集，所以使用这种方法没有明显的延迟。但是，最终我将使用更大的数据集，因此想将其切换为 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 秒，然后它挂到我需要重新启动浏览器的地步。我过去经常使用二进制搜索，但我终究无法弄清楚为什么这个不能正常工作。
编辑 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;
}
成功了。
您的二分搜索似乎有点不对：试试这个。
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;
}
我不知道你的确切情况，但代码可能会崩溃：
1) 从具有两个 X 值的数组开始。这个数组的长度为 2，所以 a = 0, b = 1, c = 0.
2) a < b, while循环执行。
3) c = floor((a + b) / 2) = floor(0.5) = 0.
4) 假设鼠标不在第一个 X 值的灵敏度范围内，所以第一个 if 分支没有命中。
5) 假设我们的X值在我们鼠标的右边，所以第二个if分支进入。这将设置 a = c，或 0，它已经是。
6) 因此，我们得到一个死循环。