Formal way of getting closest values in array in Javascript, given a value and a sorted array?
If I have an array like this:
var array = [1, 3, 4, 5, 9, 10];
And I have a value like this:
var value = 8;
I want to get this result:
var result = getClosestValues(array, value); // [5, 9]
What's the correct/preferred w开发者_如何学Pythonay to do this in javascript? It seems like this is probably a formal algorithm somewhere. Maybe like this:
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];
}
Thanks!
If the array is sorted and large, use a binary chop to find the nearest elements:
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]];
}
Otherwise, just scan from one end to the other, keeping track of the nearest values above and below the target. For this algorithm, your version is broken, unfortunately. Here's another 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];
}
For array with sorted values (data is a matrix, xIndex is the column to search, xVal is the value to sarch for, threshold is the tolerated distance (maybe 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;
}
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);
}
精彩评论