How do I get the first two closest numbers to a target from an array using lodash?

Question

I'm new to lodash and just getting the feel for functional programming with javascript. I'm using lodash 3.0.0-pre.

I have an array of numbers that are in order and a target number.

I need an array with the first and second closest numbers unless it was the last number then I just need it. How do I get that using lodash?

I found:

function getClosest(array, target) {
    var tuples = _.map(array, function(val) {
        return [val, Math.abs(val - target)];
    });
    return _.reduce(tuples, function(memo, val) {
        return (memo[1] < val[1]) ? memo : val;
    }, [-1, 999])[0];
}

I could change it to give me the closest two instead of one but I believe it will sequence through the entire array instead of just stopping once it has the two numbers it needs since it can stop when the difference in numbers starts to increase.

Answer 1

I would recommend not to use lodash looping functions here if you care about performance. As soon as you array is ordered - it's good to use a modified version of Binary search to find index of the closest value:

function closestIndex(arr, target) {
    var i = 0, j = arr.length - 1, k;   

    while (i <= j) {
       k = Math.floor((i+j) / 2);
       if (target === arr[k] || Math.abs(i - j) <= 1 ) {
           return k;
       } else if (target < arr[k]) {
           j = k-1;
       } else {
           i = k+1;
       }
    }
    return -1;
}

and then simply compare adjacent elements in the array:

if (_.isNumber(arr[closestIndex - 1]) && _.isNumber(arr[closestIndex + 1])) {
    if (Math.abs(target - arr[closestIndex - 1]) < Math.abs(target - arr[closestIndex + 1])) {
        result.push(arr[closestIndex - 1]);
    } else {
        result.push(arr[closestIndex + 1]);
    }
}

See full example here.