Формальный способ получения ближайших значений в массиве в 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];
}

Answer 2

Для массива с отсортированными значениями (данные - это матрица, xIndex - столбец для поиска, xVal - значение для поиска, порог - допустимое расстояние (возможно, 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;
}

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