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

感谢！

- Lance

---

如果数组中有一个8，它应该只返回它吗？ - Gabriele Petrioli

你是想获取最接近的2个值，还是value两侧最接近的值。例如，如果value=6，它应该返回[4,5]还是[5,9]？ - Jonathon Bolster

这个数组是否保证已经排序？ - Marcelo Cantos

是的，如果数组中包含8，则应返回8，否则返回两个相邻的值。 - Lance

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

- Marcelo Cantos

---

是的，在这里二分查找是你的好朋友。 - Daniel Pryden

你需要定义一个接近度的阈值，以便确定元素X低于目标，元素Y高于目标，然后在这两个元素之间进行扫描。很可能需要跟踪它们。因此，在测试元素之前，将其存储在这两个保留位置中之一，以便在丢弃之前进行检查。 - jcolebrand

当数组长度为奇数时，这个方法对我来说会失败。使用var mid = Math.round((lo + hi)/2);可以解决问题。 - miguelrios

@miguelrios：谢谢你指出来。我忘记了在JavaScript中除法总是浮点数。我已经修改了我的答案。 - Marcelo Cantos

@GhoulFool：线性扫描算法报告称10.1是最接近且大于等于10的值，并且不存在小于等于它的值。这有什么问题吗？顺便说一下，我刚刚调整了二分查找版本，使其表现相同。以前它会返回两个最低的值，即使它们都高于10。 - Marcelo Cantos

糟糕！我的错误。先对数组进行排序；否则，low将未定义。 - Ghoul Fool

Answer 2

对于已排序值的数组（data是矩阵，xIndex是要搜索的列，xVal是要搜索的值，threshold是可容忍的距离（可能为0））：

public static int getNearestValueIndex(double[][] data, int xIndex, Number xVal, int threshold){
    int indexMin = 0;
    int indexMax=data.length-1;

    int index;
    double val;
    double valToFind=xVal.doubleValue();
    double diff;
    index = (indexMax+indexMin)/2;
    while(index!=indexMin){

        val = data[index][xIndex];
        diff = Math.abs(valToFind-val);
        if(diff<=threshold) break;

        if(val<valToFind){
            indexMin=index;
        }else if(val>xVal.doubleValue()){
            indexMax=index;
        }
        index = (indexMax+indexMin)/2;
    }
    val = data[index][xIndex];
    if(data.length>(index+1) && Math.abs(valToFind-val)> Math.abs(valToFind-data[index+1][xIndex])){
        index=index+1;
    }

    return index;
}

- Luca Manzo

Answer 3

C 代码

#include <stdio.h>

#define moddiff(a,b) ((a > b) ? (a-b) : (b-a))

#define uint unsigned int

/* test case : sample array */
uint arr[] = { 1, 4, 9, 16, 25, 36, 49 , 64, 81 };

/* search for nearest num to key in a sorted array */
uint nrst_num(uint arr[], uint lo, uint hi, uint key) 
{
  uint mid = 0;
  uint mid_parent = 0;

  while (lo <= hi) {
    mid_parent = mid;
    mid = (lo + hi) / 2; 

    if (key == arr[mid]) {
        return mid;
    } else if (key < arr[mid]) {
        hi = mid - 1;
    } else if (key > arr[mid]) {
        lo = mid + 1;
    }   
  }

  uint ldiff = moddiff(key, arr[lo]);
  uint mdiff = moddiff(key, arr[mid]);
  uint hdiff = moddiff(key, arr[hi]);
  uint mid_parent_diff = moddiff(key, arr[mid_parent]);

  /* select the index from the lowest diff */
  if ((mid_parent_diff <= mdiff) && (mid_parent_diff <= ldiff) && (mid_parent_diff <= hdiff)) {
        return mid_parent;
  } else if ((mdiff <= mid_parent_diff) && (mdiff <= ldiff) && (mdiff <= hdiff)) {
        return mid;
  } else if ((ldiff <= mdiff) && (ldiff <= hdiff) && (ldiff <= mid_parent_diff)) {
        return lo;
  }

  return hi; 
}


int main()
{
 /* test case */
  uint key = 0;

  printf(" { 1, 4, 9, 16, 25, 36, 49 , 64, 81 }");
  uint res = nrst_num(arr, 0, 8, key);

  printf (" nearest point to key=%d is val=%d \n", key, res); 
}

- user78326

---

提供 C 代码来回答一个 JavaScript 的问题并不是很有用！ - Lee Taylor