在给定值和排序数组的情况下,在Javascript中获取最接近的值的正式方法？

Question

如果我有这样的数组:

var array = [1, 3, 4, 5, 9, 10];

我有这样的价值:

var value = 8;

我想得到这个结果:

var result = getClosestValues(array, value); // [5, 9]

在javascript中执行此操作的正确/首选方法是什么？看起来这可能是某个地方的正式算法.也许是这样的:

var getClosestValues = function(array, value) {
    var low, high = 0, value;
    for (var i = 0; i < array.length; i++) {
        if (low <= value && low < array[i])
            low = array[i];
        if (high == value && high < array[i])
            high = array[i];
    };
    return [low, high];
}

谢谢!

Answer 1

如果数组已排序且大,请使用二进制切块查找最近的元素:

var getClosestValues = function(a, x) {
    var lo = -1, hi = a.length;
    while (hi - lo > 1) {
        var mid = Math.round((lo + hi)/2);
        if (a[mid] <= x) {
            lo = mid;
        } else {
            hi = mid;
        }
    }
    if (a[lo] == x) hi = lo;
    return [a[lo], a[hi]];
}

否则,只需从一端扫描到另一端,跟踪目标上下的最近值.对于此算法,遗憾的是您的版本已损坏.这是另一个版本:

var getClosestValues = function(a, x) {
    var lo, hi;
    for (var i = a.length; i--;) {
        if (a[i] <= x && (lo === undefined || lo < a[i])) lo = a[i];
        if (a[i] >= x && (hi === undefined || hi > a[i])) hi = a[i];
    };
    return [lo, hi];
}