找到最接近给定值的索引

Question

我有一个有序数组：

btnDrag.pos = [0, 65, 131, 196, 259, 323, 388, 453, 517];

还有一个在拖动停止时触发的函数：

btnDrag.draggable({
    axis: 'x',
    containment: 'parent',
    stop: function() {
        var index = (function(){
            var new_x = btnDrag.position().left;
            // now, how to find the closest index in btnDrag.pos relative to new_x ?
            // return index;
        })();
        btnDrag.animate({
            'left': (btnDrag.pos[index] + 'px')
        });
    }
});

数组值是允许 btnDrag 停留的点（在轴“x”中）。

因此，该函数必须返回值与 btnDrag go 最接近的索引。

提前致谢。

Answer 1

由于您的数组已排序，因此最快的方法是使用二进制搜索算法的修改版本：

function closest (arr, x) {
    /* lb is the lower bound and ub the upper bound defining a subarray or arr. */
    var lb = 0, 
        ub = arr.length - 1;
    /* We loop as long as x is in inside our subarray and the length of our subarray is
       greater than 0 (lb < ub). */
    while (ub - lb > 1) {
        var m = parseInt((ub - lb + 1) / 2); // The middle value
        /* Depending on the middle value of our subarray, we update the bound. */
        if (arr[lb + m] > x) {
            ub = lb + m;
        }
        else if (arr[lb + m] < x) {
            lb = lb + m;
        }
        else {
            ub = lb + m; 
            lb = lb + m;
        }
    }
    /* After the loop, we know that the closest value is either the one at the lower or 
       upper bound (may be the same if x is in arr). */
    var clst = lb;
    if (abs(arr[lb] - x) > abs(arr[ub] - x)) {
        clst = ub;
    }
    return clst; // If you want the value instead of the index, return arr[clst]
}

这是您可以测试的小提琴：http : //jsfiddle.net/Lpzndcbm/4/

与此处提出的所有解决方案不同，该解决方案O(log(n))在O(n). 如果你不熟悉的复杂性，这意味着该算法将发现大小的数组最接近的值N在最高 O(log(N))循环，而其他人将最多发现它在N环（带N = 10000，这让因为有很大的区别log(10000) ~ 14（二进制日志） ）。

请注意，如果您的数组非常小，这可能比朴素算法慢。