从数组中向下查找最接近的数字到不同的数字
示例：我有一个这样的数组： [0,22,56,74,89] ，我想找到最接近不同数字的数字。 假设数字是72 ，在这种情况下，数组中最接近的数字是56 ，所以我们返回。 如果数字是100 ，那么它比数组中的最大数字大，所以我们返回最大的数字。 如果数字是22 ，那么它就是完全匹配，只需返回即可。 给定的数字永远不会低于0，并且数组始终排序。
我确实看到了这个问题，但它返回的最接近的数字是向上或向下靠近的数字。 无论如何，我必须让最近的一个向下返回。
我该如何开始？ 我应该使用什么逻辑？
最好没有太多的循环，因为我的代码每秒运行一次，并且已经足够CPU密集了。
您可以使用二进制搜索来获取该值。 改编自这个答案 ：
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]);
顺便说一句：这是一个快速的性能测试 （适应@Simon中的一个），它清楚地显示了二分查找的优点。
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/
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));
这是一个没有jQuery的解决方案，可以提高效率。 如果数组始终排序，则可以正常工作，无论如何都可以轻松覆盖：
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; }
逻辑：从最小数字开始，只要当前数字小于或等于测试单位，就设置result 。
注意：出于好奇只是做了一点性能测试 :)。 在不声明函数的情况下将我的代码修剪到基本部分。
正如我们所知，数组已经排序，我会将断言的所有内容都推送到一个临时数组，然后返回一个pop。
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]);
这是@Simon编辑的。 它比较它前后的最接近的数字。
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; }