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.