I have a number from minus 1000 to plus 1000 and I have an array with numbers in it. Like this:
[2, 42, 82, 122, 162, 202, 242, 282, 322, 362]
I want that the number I've got changes to the nearest number of the array.
For example I get 80 as number I want it to get 82.
This question is related to
javascript
arrays
While there were some good solutions posted here, JavaScript is a flexible language that gives us tools to solve a problem in many different ways. It all comes down to your style, of course. If your code is more functional, you'll find the reduce variation suitable, i.e.:
arr.reduce(function (prev, curr) {
return (Math.abs(curr - goal) < Math.abs(prev - goal) ? curr : prev);
});
However, some might find that hard to read, depending on their coding style. Therefore I propose a new way of solving the problem:
var findClosest = function (x, arr) {
var indexArr = arr.map(function(k) { return Math.abs(k - x) })
var min = Math.min.apply(Math, indexArr)
return arr[indexArr.indexOf(min)]
}
findClosest(80, [2, 42, 82, 122, 162, 202, 242, 282, 322, 362]) // Outputs 82
Contrary to other approaches finding the minimum value using Math.min.apply, this one doesn't require the input array arr to be sorted. We don't need to care about the indexes or sort it beforehand.
I'll explain the code line by line for clarity:
arr.map(function(k) { return Math.abs(k - x) }) Creates a new array, essentially storing the absolute values of the given numbers (number in arr) minus the input number (x). We'll look for the smallest number next (which is also the closest to the input number)Math.min.apply(Math, indexArr) This is a legit way of finding the smallest number in the array we've just created before (nothing more to it)arr[indexArr.indexOf(min)] This is perhaps the most interesting part. We have found our smallest number, but we're not sure if we should add or subtract the initial number (x). That's because we used Math.abs() to find the difference. However, array.map creates (logically) a map of the input array, keeping the indexes in the same place. Therefore, to find out the closest number we just return the index of the found minimum in the given array indexArr.indexOf(min).I've created a bin demonstrating it.
A slightly modified binary search on the array would work.
ES6
/**
* Finds the nearest value in an array of numbers.
* Example: nearestValue(array, 42)
*
* @param {Array<number>} arr
* @param {number} val the ideal value for which the nearest or equal should be found
*/
const nearestValue = (arr, val) => arr.reduce((p, n) => (Math.abs(p) > Math.abs(n - val) ? n - val : p), Infinity) + val
Examples:
let values = [1,2,3,4,5]
console.log(nearestValue(values, 10)) // --> 5
console.log(nearestValue(values, 0)) // --> 1
console.log(nearestValue(values, 2.5)) // --> 2
values = [100,5,90,56]
console.log(nearestValue(values, 42)) // --> 56
values = ['100','5','90','56']
console.log(nearestValue(values, 42)) // --> 56
I like the approach from Fusion, but there's a small error in it. Like that it is correct:
function closest(array, number) {
var num = 0;
for (var i = array.length - 1; i >= 0; i--) {
if(Math.abs(number - array[i]) < Math.abs(number - array[num])){
num = i;
}
}
return array[num];
}
It it also a bit faster because it uses the improved for loop.
At the end I wrote my function like this:
var getClosest = function(number, array) {
var current = array[0];
var difference = Math.abs(number - current);
var index = array.length;
while (index--) {
var newDifference = Math.abs(number - array[index]);
if (newDifference < difference) {
difference = newDifference;
current = array[index];
}
}
return current;
};
I tested it with console.time() and it is slightly faster than the other function.
ES6 (ECMAScript 2015) Version:
const counts = [4, 9, 15, 6, 2];
const goal = 5;
const output = counts.reduce((prev, curr) => Math.abs(curr - goal) < Math.abs(prev - goal) ? curr : prev);
console.log(output);For reusability you can wrap in a curry function that supports placeholders (http://ramdajs.com/0.19.1/docs/#curry or https://lodash.com/docs#curry). This gives lots of flexibility depending on what you need:
const getClosest = _.curry((counts, goal) => {
return counts.reduce((prev, curr) => Math.abs(curr - goal) < Math.abs(prev - goal) ? curr : prev);
});
const closestToFive = getClosest(_, 5);
const output = closestToFive([4, 9, 15, 6, 2]);
console.log(output);<script src="https://cdn.jsdelivr.net/npm/[email protected]/lodash.min.js"></script>The most efficient would be a binary search. However even simple solutions can exit when the next number is a further match from the current. Nearly all solutions here are not taking into account that the array is ordered and iterating though the whole thing :/
const closest = (orderedArray, value, valueGetter = item => item) =>_x000D_
orderedArray.find((item, i) =>_x000D_
i === orderedArray.length - 1 ||_x000D_
Math.abs(value - valueGetter(item)) < Math.abs(value - valueGetter(orderedArray[i + 1])));_x000D_
_x000D_
var data = [2, 42, 82, 122, 162, 202, 242, 282, 322, 362];_x000D_
_x000D_
console.log('21 -> 2', closest(data, 21) === 2);_x000D_
console.log('22 -> 42', closest(data, 22) === 42); // equidistant between 2 and 42, select highest_x000D_
console.log('23 -> 42', closest(data, 23) === 42);_x000D_
console.log('80 -> 82', closest(data, 80) === 82);This can be run on non-primitives too e.g. closest(data, 21, item => item.age)
Change find to findIndex to return the index in the array.
Another variant here we have circular range connecting head to toe and accepts only min value to given input. This had helped me get char code values for one of the encryption algorithm.
function closestNumberInCircularRange(codes, charCode) {
return codes.reduce((p_code, c_code)=>{
if(((Math.abs(p_code-charCode) > Math.abs(c_code-charCode)) || p_code > charCode) && c_code < charCode){
return c_code;
}else if(p_code < charCode){
return p_code;
}else if(p_code > charCode && c_code > charCode){
return Math.max.apply(Math, [p_code, c_code]);
}
return p_code;
});
}
A simpler way with O(n) time complexity is to do this in one iteration of the array. This method is intended for unsorted arrays.
Following is a javascript example, here from the array we find the number which is nearest to "58".
var inputArr = [150, 5, 200, 50, 30];
var search = 58;
var min = Math.min();
var result = 0;
for(i=0;i<inputArr.length;i++) {
let absVal = Math.abs(search - inputArr[i])
if(min > absVal) {
min=absVal;
result = inputArr[i];
}
}
console.log(result); //expected output 50 if input is 58This will work for positive, negative, decimal numbers as well.
Math.min() will return Infinity.
The result will store the value nearest to the search element.
I don't know if I'm supposed to answer an old question, but as this post appears first on Google searches, I hoped that you would forgive me adding my solution & my 2c here.
Being lazy, I couldn't believe that the solution for this question would be a LOOP, so I searched a bit more and came back with filter function:
var myArray = [2, 42, 82, 122, 162, 202, 242, 282, 322, 362];
var myValue = 80;
function BiggerThan(inArray) {
return inArray > myValue;
}
var arrBiggerElements = myArray.filter(BiggerThan);
var nextElement = Math.min.apply(null, arrBiggerElements);
alert(nextElement);
That's all !
All answers so far concentrate on searching through the whole array. Considering your array is sorted already and you really only want the nearest number this is probably the fastest solution:
var a = [2, 42, 82, 122, 162, 202, 242, 282, 322, 362];_x000D_
var target = 90000;_x000D_
_x000D_
/**_x000D_
* Returns the closest number from a sorted array._x000D_
**/_x000D_
function closest(arr, target) {_x000D_
if (!(arr) || arr.length == 0)_x000D_
return null;_x000D_
if (arr.length == 1)_x000D_
return arr[0];_x000D_
_x000D_
for (var i = 1; i < arr.length; i++) {_x000D_
// As soon as a number bigger than target is found, return the previous or current_x000D_
// number depending on which has smaller difference to the target._x000D_
if (arr[i] > target) {_x000D_
var p = arr[i - 1];_x000D_
var c = arr[i]_x000D_
return Math.abs(p - target) < Math.abs(c - target) ? p : c;_x000D_
}_x000D_
}_x000D_
// No number in array is bigger so return the last._x000D_
return arr[arr.length - 1];_x000D_
}_x000D_
_x000D_
// Trying it out_x000D_
console.log(closest(a, target));Note that the algorithm can be vastly improved e.g. using a binary tree.
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;
class CompareFunctor
{
public:
CompareFunctor(int n) { _n = n; }
bool operator()(int & val1, int & val2)
{
int diff1 = abs(val1 - _n);
int diff2 = abs(val2 - _n);
return (diff1 < diff2);
}
private:
int _n;
};
int Find_Closest_Value(int nums[], int size, int n)
{
CompareFunctor cf(n);
int cn = *min_element(nums, nums + size, cf);
return cn;
}
int main()
{
int nums[] = { 2, 42, 82, 122, 162, 202, 242, 282, 322, 362 };
int size = sizeof(nums) / sizeof(int);
int n = 80;
int cn = Find_Closest_Value(nums, size, n);
cout << "\nClosest value = " << cn << endl;
cin.get();
}
This solution uses ES5 existential quantifier Array#some, which allows to stop the iteration, if a condition is met.
Opposit of Array#reduce, it does not need to iterate all elements for one result.
Inside the callback, an absolute delta between the searched value and actual item is taken and compared with the last delta. If greater or equal, the iteration stops, because all other values with their deltas are greater than the actual value.
If the delta in the callback is smaller, then the actual item is assigned to the result and the delta is saved in lastDelta.
Finally, smaller values with equal deltas are taken, like in the below example of 22, which results in 2.
If there is a priority of greater values, the delta check has to be changed from:
if (delta >= lastDelta) {
to:
if (delta > lastDelta) {
// ^^^ without equal sign
This would get with 22, the result 42 (Priority of greater values).
This function needs sorted values in the array.
function closestValue(array, value) {_x000D_
var result,_x000D_
lastDelta;_x000D_
_x000D_
array.some(function (item) {_x000D_
var delta = Math.abs(value - item);_x000D_
if (delta >= lastDelta) {_x000D_
return true;_x000D_
}_x000D_
result = item;_x000D_
lastDelta = delta;_x000D_
});_x000D_
return result;_x000D_
}_x000D_
_x000D_
var data = [2, 42, 82, 122, 162, 202, 242, 282, 322, 362];_x000D_
_x000D_
console.log(21, closestValue(data, 21)); // 2_x000D_
console.log(22, closestValue(data, 22)); // 2 smaller value_x000D_
console.log(23, closestValue(data, 23)); // 42_x000D_
console.log(80, closestValue(data, 80)); // 82function closestValue(array, value) {_x000D_
var result,_x000D_
lastDelta;_x000D_
_x000D_
array.some(function (item) {_x000D_
var delta = Math.abs(value - item);_x000D_
if (delta > lastDelta) {_x000D_
return true;_x000D_
}_x000D_
result = item;_x000D_
lastDelta = delta;_x000D_
});_x000D_
return result;_x000D_
}_x000D_
_x000D_
var data = [2, 42, 82, 122, 162, 202, 242, 282, 322, 362];_x000D_
_x000D_
console.log(21, closestValue(data, 21)); // 2_x000D_
console.log(22, closestValue(data, 22)); // 42 greater value_x000D_
console.log(23, closestValue(data, 23)); // 42_x000D_
console.log(80, closestValue(data, 80)); // 82For a small range, the simplest thing is to have a map array, where, eg, the 80th entry would have the value 82 in it, to use your example. For a much larger, sparse range, probably the way to go is a binary search.
With a query language you could query for values some distance either side of your input number and then sort through the resulting reduced list. But SQL doesn't have a good concept of "next" or "previous", to give you a "clean" solution.
ES5 Version:
var counts = [4, 9, 15, 6, 2],_x000D_
goal = 5;_x000D_
_x000D_
var closest = counts.reduce(function(prev, curr) {_x000D_
return (Math.abs(curr - goal) < Math.abs(prev - goal) ? curr : prev);_x000D_
});_x000D_
_x000D_
console.log(closest);Here's the pseudo-code which should be convertible into any procedural language:
array = [2, 42, 82, 122, 162, 202, 242, 282, 322, 362]
number = 112
print closest (number, array)
def closest (num, arr):
curr = arr[0]
foreach val in arr:
if abs (num - val) < abs (num - curr):
curr = val
return curr
It simply works out the absolute differences between the given number and each array element and gives you back one of the ones with the minimal difference.
For the example values:
number = 112 112 112 112 112 112 112 112 112 112
array = 2 42 82 122 162 202 242 282 322 362
diff = 110 70 30 10 50 90 130 170 210 250
|
+-- one with minimal absolute difference.
As a proof of concept, here's the Python code I used to show this in action:
def closest (num, arr):
curr = arr[0]
for index in range (len (arr)):
if abs (num - arr[index]) < abs (num - curr):
curr = arr[index]
return curr
array = [2, 42, 82, 122, 162, 202, 242, 282, 322, 362]
number = 112
print closest (number, array)
And, if you really need it in Javascript, see below for a complete HTML file which demonstrates the function in action:
<html>
<head></head>
<body>
<script language="javascript">
function closest (num, arr) {
var curr = arr[0];
var diff = Math.abs (num - curr);
for (var val = 0; val < arr.length; val++) {
var newdiff = Math.abs (num - arr[val]);
if (newdiff < diff) {
diff = newdiff;
curr = arr[val];
}
}
return curr;
}
array = [2, 42, 82, 122, 162, 202, 242, 282, 322, 362];
number = 112;
alert (closest (number, array));
</script>
</body>
</html>
Now keep in mind there may be scope for improved efficiency if, for example, your data items are sorted (that could be inferred from the sample data but you don't explicitly state it). You could, for example, use a binary search to find the closest item.
You should also keep in mind that, unless you need to do it many times per second, the efficiency improvements will be mostly unnoticable unless your data sets get much larger.
If you do want to try it that way (and can guarantee the array is sorted in ascending order), this is a good starting point:
<html>
<head></head>
<body>
<script language="javascript">
function closest (num, arr) {
var mid;
var lo = 0;
var hi = arr.length - 1;
while (hi - lo > 1) {
mid = Math.floor ((lo + hi) / 2);
if (arr[mid] < num) {
lo = mid;
} else {
hi = mid;
}
}
if (num - arr[lo] <= arr[hi] - num) {
return arr[lo];
}
return arr[hi];
}
array = [2, 42, 82, 122, 162, 202, 242, 282, 322, 362];
number = 112;
alert (closest (number, array));
</script>
</body>
</html>
It basically uses bracketing and checking of the middle value to reduce the solution space by half for each iteration, a classic O(log N) algorithm whereas the sequential search above was O(N):
0 1 2 3 4 5 6 7 8 9 <- indexes
2 42 82 122 162 202 242 282 322 362 <- values
L M H L=0, H=9, M=4, 162 higher, H<-M
L M H L=0, H=4, M=2, 82 lower/equal, L<-M
L M H L=2, H=4, M=3, 122 higher, H<-M
L H L=2, H=3, difference of 1 so exit
^
|
H (122-112=10) is closer than L (112-82=30) so choose H
As stated, that shouldn't make much of a difference for small datasets or for things that don't need to be blindingly fast, but it's an option you may want to consider.
My answer to a similar question is accounting for ties too and it is in plain Javascript, although it doesn't use binary search so it is O(N) and not O(logN):
var searchArray= [0, 30, 60, 90];
var element= 33;
function findClosest(array,elem){
var minDelta = null;
var minIndex = null;
for (var i = 0 ; i<array.length; i++){
var delta = Math.abs(array[i]-elem);
if (minDelta == null || delta < minDelta){
minDelta = delta;
minIndex = i;
}
//if it is a tie return an array of both values
else if (delta == minDelta) {
return [array[minIndex],array[i]];
}//if it has already found the closest value
else {
return array[i-1];
}
}
return array[minIndex];
}
var closest = findClosest(searchArray,element);
Here is the Code snippet to find the closest element to a number from an array in Complexity O(nlog(n)) :-
Input :- {1,60,0,-10,100,87,56} Element:- 56 Closest Number in Array:- 60
Source Code (Java):
package com.algo.closestnumberinarray;
import java.util.TreeMap;
public class Find_Closest_Number_In_Array {
public static void main(String arsg[]) {
int array[] = { 1, 60, 0, -10, 100, 87, 69 };
int number = 56;
int num = getClosestNumber(array, number);
System.out.println("Number is=" + num);
}
public static int getClosestNumber(int[] array, int number) {
int diff[] = new int[array.length];
TreeMap<Integer, Integer> keyVal = new TreeMap<Integer, Integer>();
for (int i = 0; i < array.length; i++) {
if (array[i] > number) {
diff[i] = array[i] - number;
keyVal.put(diff[i], array[i]);
} else {
diff[i] = number - array[i];
keyVal.put(diff[i], array[i]);
}
}
int closestKey = keyVal.firstKey();
int closestVal = keyVal.get(closestKey);
return closestVal;
}
}
To Find Two Closest Number in array
function findTwoClosest(givenList, goal) {
var first;
var second;
var finalCollection = [givenList[0], givenList[1]];
givenList.forEach((item, firtIndex) => {
first = item;
for (let i = firtIndex + 1; i < givenList.length; i++) {
second = givenList[i];
if (first + second < goal) {
if (first + second > finalCollection[0] + finalCollection[1]) {
finalCollection = [first, second];
}
}
}
});
return finalCollection;
}
var counts = [2, 42, 82, 122, 162, 202, 242, 282, 322, 362]
var goal = 80;
console.log(findTwoClosest(counts, goal));
Working code as below:
var array = [2, 42, 82, 122, 162, 202, 242, 282, 322, 362];_x000D_
_x000D_
function closest(array, num) {_x000D_
var i = 0;_x000D_
var minDiff = 1000;_x000D_
var ans;_x000D_
for (i in array) {_x000D_
var m = Math.abs(num - array[i]);_x000D_
if (m < minDiff) {_x000D_
minDiff = m;_x000D_
ans = array[i];_x000D_
}_x000D_
}_x000D_
return ans;_x000D_
}_x000D_
console.log(closest(array, 88));All of the solutions are over-engineered.
It is as simple as:
const needle = 5;
const haystack = [1, 2, 3, 4, 5, 6, 7, 8, 9];
haystack.sort((a, b) => {
return Math.abs(a - needle) - Math.abs(b - needle);
})[0];
// 5
Source: Stackoverflow.com