algorithm - Formal way of getting closest values in array in Javascript, given a value and a sorted array?

Question

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 way 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!

Answer 1

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