Manière formelle d'obtenir les valeurs les plus proches dans le tableau en Javascript, étant donné une valeur et un tableau trié?

Si j'ai un tableau comme ceci:

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

Et j'ai une valeur comme ceci:

var value = 8;

Je veux obtenir ce résultat:

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

Ce qui est de la bonne/meilleure façon de le faire en javascript? Il semble que ce est probablement l'une formelle de l'algorithme de quelque part. Peut-être comme ceci:

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

Merci!

source d'informationauteur Lance Pollard

  1. 33

    Si le tableau est trié et grandes, utiliser un binaire chop pour trouver le plus proche éléments:

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

    Sinon, il suffit de numériser à partir d'une extrémité à l'autre, en gardant une trace de la plus proche des valeurs au-dessus et au-dessous de la cible. Pour cet algorithme, votre version est cassée, malheureusement. Voici une autre version:

    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];
}
  2. 0

    Pour un tableau avec les valeurs triées (données est une matrice, xIndex est la colonne de recherche, xVal est la valeur de sarch, du seuil de la tolérance de distance (peut-être 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;
}
  3. -5

    C-code

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