Find the number in an array that is closest to a given number

Question

I have an Array of integers in javascript, [5,10,15,20,25,30,35] when given a number x, how can I find the element in the array that is closest to that number?

If the number is over a value, but less than halfway to the next number, I would choose the smaller value, if it were over halfway to the next number, I would choose the higher number.

For example 7 would return 5, but 8 would return 10. How can I accomplish this? Any help or tips would be appreciated. I have searched and cannot find a solution. I'm sure this is sort of common.

Answer 1

Probably the easiest thing to do is sort based on distance from the reference value x, and then take the first item.

The built-in Array.prototype.sort() can take a comparison function which will be called for pairs of values from the array. Then the key is simply to pass in a comparison function which compares the two values based on their distance from the reference value x.

let x = 8;
let array = [5, 10, 15, 20, 25, 30, 35];
let closest = array.sort( (a, b) => Math.abs(x - a) - Math.abs(x - b) )[0];

See this simple demo.

Answer 2

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

If using a functional approach is applicable then you can map the set to tuples of (value, distance) then reduce that set of tuples to the tuple with the smallest distance. We return the value in that tuple.

To explain the useage of _.map. You map all the values in your array to new values and the function will return the array of new values. In this case an array of tuples.

To explain the useage of _.reduce. You reduce the array to a single value. You pass in an array and a memo. The memo is your "running counter" as you move through the array. In this case we check whether the current tuple is closer then the memo and if so make it the memo. We then return the memo at the end.

The code snippet above relies on underscore.js to remove the nitty gritty of functional style javascript

Answer 3

Your example list is sorted. If this is always the case, then binary search for your number. If you don't find the exact number, make the binary search end off by checking the two numbers around where the number would be and return the closest. Be careful with edge cases where all numbers are greater or are all smaller than the target number

If the list isn't always sorted, then go through the list keeping track of the largest number <= the target number and the smallest number >= the target number. Return the one that's closest to the target.

In either solution, you'll need to decide which side to favour if for example you're searching for 2 in [1, 3].

Answer 4

Create a temporary array of the same size as your original array, and populate it with the differences between your x and the array element.

For example, let the temporary array be temp[], and your original array be a[]:

temp[i]=Math.abs(x-a[i]);

Then, return the index of the minimum value in temp[] to the user.

Answer 5

I created my own function since i could not find any that meets my requeriments.

    function closest_number(quantities, number, closest_factor)
    {
        if (closest_factor == 'ceil')
        {
            quantities.sort(function(a, b)
                {
                    return a - b
                }
            );

            for (var i = 0; i < quantities.length; i++)
            {
                if (quantities[i] >= number)
                {
                    return quantities[i];
                }

                last_value = quantities[i];
            }

            return last_value;
        }
        else if (closest_factor == 'floor')
        {
            quantities.sort(function(a, b)
                {
                    return a - b
                }
            );

            min_value = quantities[0];

            for (var i = 0; i < quantities.length; i++)
            {
                if (number == quantities[i])
                {
                    return number;
                }
                else if (quantities[i] < number)
                {
                    min_value = quantities[i];
                }
                else if(quantities[i] > number)
                {
                    return min_value;
                }           
            }

            return min_value;
        }
        else
        {
            return false;
        }
    };

Answer 6

Assuming the array is sorted, step through each adjacent pair of integers in the array. For each pair (say "5 and 10" or "20 and 25"), test if x is in between them, and if so, return whichever one is closer to x (with a bias towards the lower one).

You would also need a special case for when x is less than the first number (return the first number) or greater than the last number (return the last number).

If the array is not sorted, sort it first.

Answer 7

Since Array.reduce is a reality for so long (even IE9 supports it), the problem is easily solvable with it. This way, no need to sort the array first (no array mutation at all):

var numbers = [20, 25, 30, 35, 5, 10, 15], x = 7;

var output = numbers.reduce(function (prev, curr) {
  return Math.abs(curr - x) < Math.abs(prev - x) ? curr : prev
});

console.log(output);

You can go further and solve it with only one line of ES6 (ECMAScript 2015) syntax, by using an arrow function (but with no IE support in this case):

const numbers = [20, 25, 30, 35, 5, 10, 15], x = 7;

const output = numbers.reduce((prev, curr) => Math.abs(curr - x) < Math.abs(prev - x) ? curr : prev);

console.log(output);

Of course, for flexibility and reusability, it's easy to make it as a function:

const closest = (array, goal) => array.reduce((prev, curr) => Math.abs(curr - goal) < Math.abs(prev - goal) ? curr : prev);

console.log(closest([20, 25, 30, 35, 5, 10, 15], 7));
console.log(closest([20, 25, 30, 35, 5, 10, 15], 8));
console.log(closest([1, 5, 7], -5));
console.log(closest([1, 5, 7], 4));
console.log(closest([1, 5, 7], 20));