Finding the closest number downward to a different number from an array

Question

Example: I have an array like this: [0,22,56,74,89] and I want to find the closest number downward to a different number. Let's say that the number is 72, and in this case, the closest number down in the array is 56, so we return that. If the number is 100, then it's bigger than the biggest number in the array, so we return the biggest number. If the number is 22, then it's an exact match, just return that. The given number can never go under 0, and the array is always sorted.

I did see this question but it returns the closest number to whichever is closer either upward or downward. I must have the closest one downward returned, no matter what.

How do I start? What logic should I use?

Preferably without too much looping, since my code is run every second, and it's CPU intensive enough already.

Answer 1

You can use a binary search for that value. Adapted from this answer:

function index(arr, compare) { // binary search, with custom compare function
    var l = 0,
        r = arr.length - 1;
    while (l <= r) {
        var m = l + ((r - l) >> 1);
        var comp = compare(arr[m]);
        if (comp < 0) // arr[m] comes before the element
            l = m + 1;
        else if (comp > 0) // arr[m] comes after the element
            r = m - 1;
        else // arr[m] equals the element
            return m;
    }
    return l-1; // return the index of the next left item
                // usually you would just return -1 in case nothing is found
}
var arr = [0,22,56,74,89];
var i=index(arr, function(x){return x-72;}); // compare against 72
console.log(arr[i]);

Btw: Here is a quick performance test (adapting the one from @Simon) which clearly shows the advantages of binary search.

Answer 2

var theArray = [0,22,56,74,89];
var goal = 56;
var closest = null;

$.each(theArray, function(){
  if (this <= goal && (closest == null || (goal - this) < (goal - closest))) {
    closest = this;
  }
});
alert(closest);

jsFiddle http://jsfiddle.net/UCUJY/1/