Search for the closest number down to another number from the array

Question

Example: I have an array like this: [0,22,56,74,89] , and I want to find the closest number down to another number. Let's say that the number is 72 , and in this case the closest number is down in the array 56 , so we return this. If the number is 100 , then it is greater than the largest number in the array, so we return the largest number. If the number 22 , then this is an exact match, just return it. This number can never be under 0, and the array is always sorted.

I saw this question , but it returns the closest number depending on which is closer either up or down. I should have the one closest down, no matter what.

How do i get started? What logic should I use?

Preferably, if there are not too many cycles, as my code runs every second, and this processor is already quite intense.

Answer 1

You can use binary search for this 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's a quick performance test (adapting one from @Simon) that clearly shows the benefits 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/

Answer 3

Here's a jQuery-free solution for greater efficiency. It works if the array is always sorted, which can be easily covered:

 var test = 72, arr = [0,56,22,89,74].sort(); // just sort it generally if not sure about input, not really time consuming function getClosestDown(test, arr) { var num = result = 0; for(var i = 0; i < arr.length; i++) { num = arr[i]; if(num <= test) { result = num; } } return result; } 

Logic: start with the smallest number and just set the result while the current number is less than or equal to the tested one.

Note. Just done a little performance test out of curiosity :). Truncated my code to the necessary part without declaring a function.

Answer 4

 Array.prototype.getClosestDown = function(find) { function getMedian(low, high) { return (low + ((high - low) >> 1)); } var low = 0, high = this.length - 1, i; while (low <= high) { i = getMedian(low,high); if (this[i] == find) { return this[i]; } if (this[i] > find) { high = i - 1; } else { low = i + 1; } } return this[Math.max(0, low-1)]; } alert([0,22,56,74,89].getClosestDown(75)); 

Answer 5

As we know, the array is sorted, I would click anything that says less than our given value in the temporary array, and then return a popup message.

 var getClosest = function (num, array) { var temp = [], count = 0, length = a.length; for (count; count < length; count += 1) { if (a[count] <= num) { temp.push(a[count]); } else { break; } } return temp.pop(); } getClosest(23, [0,22,56,74,89]); 

Answer 6

Edited here by @Simon. he compares the nearest number before and after it.

 var test = 24, arr = [76,56,22,89,74].sort(); // just sort it generally if not sure about input, not really time consuming function getClosest(test, arr) { var num = result = 0; var flag = 0; for(var i = 0; i < arr.length; i++) { num = arr[i]; if(num < test) { result = num; flag = 1; }else if (num == test) { result = num; break; }else if (flag == 1) { if ((num - test) < (Math.abs(arr[i-1] - test))){ result = num; } break; }else{ break; } } return result; } 

Answer 7

Here is the ES6 version using Reduce referenced by the OP. Inspired by this answer, get the closest number from the array

The search array is always sorted, so this works.

 const nearestBelow = (input, lookup) => lookup.reduce((prev, curr) => input >= curr ? curr : prev); const counts = [0,22,56,74,89]; const goal = 72; nearestBelow(goal, counts); // result is 56. 

Not as fast as binary search (by and large), but better than loop and jQuery grep https://jsperf.com/test-a-closest-number-function/7