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

一尘不染

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

algorithm

如果我有这样的数组：

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

谢谢！

阅读 233

2020-07-28

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

2020-07-28