Formaler Weg zum Erhalten der nächsten Werte im Array in Javascript, bei einem gegebenen Wert und einem sortierten Array?

Question

Wenn ich habe ein Array wie folgt aus:

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

Und ich habe einen Wert wie folgt aus:

var value = 8; 

Ich möchte dieses Ergebnis erhalten:

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

Was die richtige ist/bevorzugte Möglichkeit, dies in Javascript zu tun? Es scheint, dass dies wahrscheinlich irgendwo ein formeller Algorithmus ist. Vielleicht so:

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

Vielen Dank!

Answer 1

Wenn das Array sortiert und groß, verwenden Sie eine binäre hacken die nächsten Elemente zu finden:

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

Andernfalls scannen nur von einem Ende zum anderen, der nächstgelegenen Werte über und unter die Verfolgung der Ziel. Für diesen Algorithmus ist deine Version leider kaputt. Hier ist eine andere 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]; 
} 

Answer 2

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

Answer 3

Bei Array mit sortierten Werten (Daten eine Matrix ist, ist xIndex die Säule zu suchen, xVal der Wert ist, für Sarch, Schwelle der IS tolerierte Entfernung (vielleicht 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; 
}