答

对数组稍作修改的二进制搜索将起作用。

+1

啧啧，这是奇怪的 - 显然有人不喜欢二分搜索。（即使认为这是最好的通用解决方案） – 2011-12-21 04:28:02

答

对于一个小范围来说，最简单的事情就是创建一个地图数组，其中例如第80个条目的值为82，以使用您的示例。对于更大，更稀疏的范围，可能要走的路是二分搜索。

使用查询语言，您可以在输入数字的任意一边查询值，然后对结果缩小列表进行排序。但是SQL没有一个好的“下一个”或“之前”的概念，给你一个“干净”的解决方案。

答

这里是伪代码应兑换成任何程序语言：

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

它运行良好的给定数量和每个数组元素之间的绝对差异，并给你回用的那些之一最小的差异。

对于示例值：

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.

由于概念证明，这里是我用行动来表明这一点的Python代码：

而且，如果你真的在Javascript中需要它，请参阅下面的完整HTML文件，其中演示了该功能的实际操作：

<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>

现在记住有可能是为了提高效率，如果范围，例如，您的数据项进行排序（可能从样本数据来推断，但是你并没有明确说明的话）。例如，您可以使用二进制搜索来查找最近的项目。

你也应该记住，除非你需要做的是每秒很多次，效率的提高将主要容易被忽视的，除非你的数据集获得多大。

如果做想尝试一下这种方式（并能保证阵列按升序排序），这是一个很好的起点：

<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>

它主要采用bracketing和的检查中间值减少一半解空间对于每次迭代，一个经典O(log N)算法而顺序搜索上述是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

如上所述，该不应该对小数据集或不需要需要非常快速的事情有所作为，但这是您可能需要考虑的一个选项。

+1

@micha，我已经添加了eqivalent JS代码到答案，它只是花了一段时间才从一个我更习惯于更改语言:-) – paxdiablo 2011-12-21 04:46:10

+2

该算法的运行时间太差如果你有大的数据集。 – 2015-04-21 08:14:44

+3

@ ylun.ca，因为在数据排序的问题中没有_explicit_语句（该例子被排序但可能是巧合的），所以你不能得到比O（n）更好的效率。无论如何，对于数据集的大小来说，效率大都是无关紧要的。但是你的观点是有效的，所以我会为此添加注释以希望使答案更加完整。 – paxdiablo 2015-04-25 23:14:26

答

工作的代码如下：

var array = [2, 42, 82, 122, 162, 202, 242, 282, 322, 362]; 

function closest(array,num){ 
    var i=0; 
    var minDiff=1000; 
    var ans; 
    for(i in array){ 
     var m=Math.abs(num-array[i]); 
     if(m<minDiff){ 
       minDiff=m; 
       ans=array[i]; 
      } 
     } 
    return ans; 
} 
alert(closest(array,88));

+8

越多越好。 – 2011-12-21 13:19:04

+5

我认为这是一个更好的解决方案，因为它只使用JavaScript。接受的答案使用了jQuery，这在原始问题中没有提到，以及其他人在看这个问题时可能没有使用。 – 2014-04-14 22:42:18

答

ES5版本：

var counts = [4, 9, 15, 6, 2], 
 
    goal = 5; 
 

 
var closest = counts.reduce(function(prev, curr) { 
 
    return (Math.abs(curr - goal) < Math.abs(prev - goal) ? curr : prev); 
 
}); 
 

 
console.log(closest);

+2

这是相当NEAT。 – 2014-01-17 16:51:43

+0

的缺点是，它只有在reduce的回调函数与声明的变量名称相同的范围内调用时才有效。既然你不能通过'目标'来减少，你必须在全局范围内引用它。 – 7yl4r 2015-02-06 15:09:17

+3

也可以使用更高阶的函数来做到这一点。 – dmp 2015-04-25 19:45:12

答

我不知道是不是我应该回答一个老问题，但作为这篇文章首先出现在谷歌搜索，我希望你原谅我在我的2c这里添加我的解决方案&。

懒惰，我简直不敢相信，对于这个问题的解决将是一个循环，所以我搜索了一点，与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);

这一切！

+1

那么下界是什么？你总是使用下一个更高的值。但是你的方法让我想起了'goog.math.clamp'（谷歌关闭）只是数组而不关心下限。 – noob 2014-04-06 08:55:19

+0

您的解决方案从阵列中返回下一个更高的数字。无论是最近的还是确切的价值都没有找到。 – 2014-08-01 22:44:24

答

对于排序的阵列（线性搜索）

所有答案为止集中通过整个阵列搜索。考虑到你的数组已经排序，你真的只想最接近的数字这可能是最快的解决方案：

var a = [2, 42, 82, 122, 162, 202, 242, 282, 322, 362]; 
var target = 90000; 

/** 
* Returns the closest number from a sorted array. 
**/ 
function closest(arr, target) { 
    if (!(arr) || arr.length == 0) 
     return null; 
    if (arr.length == 1) 
     return arr[0]; 

    for (var i=1; i<arr.length; i++) { 
     // As soon as a number bigger than target is found, return the previous or current 
     // number depending on which has smaller difference to the target. 
     if (arr[i] > target) { 
      var p = arr[i-1]; 
      var c = arr[i] 
      return Math.abs(p-target) < Math.abs(c-target) ? p : c; 
     } 
    } 
    // No number in array is bigger so return the last. 
    return arr[arr.length-1]; 
} 

// Trying it out 
console.log(closest(arr, target));

注意，该算法可以大大提高例如使用二叉树。

+0

虽然这里的这个策略很好，但有几个错别字。例如'a [i]'或'i [0]'。 – 2017-03-09 16:10:50

+1

谢谢，@WesleyWorkman。只是修复它们。我希望我得到了一切。顺便说一句，你也可以编辑他人的答案。 – 2017-03-25 08:14:28

+0

我需要在上面的回答代码中进行修正以获得更高的最接近的值吗？例如：[110,111,120,140,148,149,155,177,188,190]如果我搜索150，我应该得到155而不是149.我试过但发现难以解决这个问题。能否请你帮忙。谢谢 – user1199842 2018-01-03 14:44:13

答

我的回答类似的问题被占的关系也是一样，它是在普通的JavaScript，尽管它不使用二进制搜索所以它是O（N），而不是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);

https://stackoverflow.com/a/26429528/986160

答

ES6（2015）版本：

const counts = [4, 9, 15, 6, 2]; 
const goal = 5; 

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

可重用性，你可以在支持占位符（http://ramdajs.com/0.19.1/docs/#curry或咖喱功能包）。这给你很大的灵活性，取决于你需要什么：

const getClosest = curry((counts, goal) => { 
    return counts 
    .reduce((prev, curr) => Math.abs(curr - goal) < Math.abs(prev - goal) ? curr : prev); 
}); 

const closestTo5 = getClosest(_, 5); 
const closestTo = getClosest([4, 9, 15, 6, 2]);

答

我喜欢融合的方法，但它有一个小错误。这是正确的：

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

它也快一点，因为它使用改进的for循环。

最后我写我的功能是这样的：

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

我console.time()测试，它比其他函数稍快。

+0

嘿，你能解释为什么它是一个'改进的循环'吗？反转循环并不总是一种性能改进。 – A1rPun 2016-03-01 15:43:56

+0

当你声明'i'时，你只评估'.length'一次，而对于这个循环。但我认为'var i = arr.length; while（i--）{}'会更快 – Jon 2016-03-03 07:34:39

+0

我更新了我的答案。我把它改成'while'。现在它更快。 – Jon 2016-03-03 07:44:09

答

工程与无序阵列

虽然在这里发布了一些很好的解决方案，JavaScript是一种灵活的语言，让我们工具许多不同的方式来解决问题。当然，这一切都归结于你的风格。如果你的代码具有更多的功能，你会发现reduce variation合适的，即：

arr.reduce(function (prev, curr) { 
    return (Math.abs(curr - goal) < Math.abs(prev - goal) ? curr : prev); 
    });

然而，有些人可能会发现难以阅读，这取决于它们的编码风格。因此，我提出解决问题的新方法：

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([2, 42, 82, 122, 162, 202, 242, 282, 322, 362], 80) // Outputs 82

相反other approaches发现使用Math.min.apply最小值，这一个不需要输入数组arr进行排序。我们不需要关心索引或事先对索引进行分类。

我将通过线为了清楚解释代码行：

arr.map(function(k) { return Math.abs(k - x) })创建一个新数组，基本上存储给定数字的绝对值（以arr数）减去输入编号（x）。我们来看看下个最小号（这也是最接近输入数字）
Math.min.apply(Math, indexArr)这是发现我们刚刚之前（没有更多的话）创建的阵列中最小号的合法的方式
arr[indexArr.indexOf(min)]这也许是最有趣的部分。我们找到了最小的数字，但我们不确定是否应该添加或减去初始数字（x）。这是因为我们使用Math.abs()来找出差异。但是，array.map创建（逻辑上）输入数组的映射，使索引保持在同一位置。因此，要找出最接近的数字，我们只返回给定数组indexArr.indexOf(min)中找到的最小值的索引。

我创建了一个bin来演示它。

+0

Downvoters，请解释为什么这不是一个好的答案或为什么你不觉得它合适。谢谢。 – 2016-10-09 09:52:16

+1

我不知道，但我想你可能会有性能怀疑，因为这实际上是'3n'，它是ES5，即使你在2016年回答，其他解决方案也很好，即使这个清醒地问这个问题的noob不是程序员当时。 – noob 2016-10-10 17:50:06

+0

恕我直言，我不明白ES6版本的答案如何使它更好，除了使用'const'（箭头函数的作用是什么？）。有些人可能会认为它更不可读。最重要的是，我怀疑ES6在一般的atm中表现不错，请记住，我们仍然运行大多数ES5并使用Babel来转换ES6代码。最后，我认为表演的论点很荒谬。我挑战你对所有方法进行基准测试，并查看浏览器中哪些方法最慢。我不知道你在你的生活中做了多少基准测试，但是从它的外观来看 - 你很惊喜。 – 2016-10-10 18:32:12

答

这是一个建议与ES5 existential quantifierArray#some，它允许停止迭代，如果满足条件。

对Array#reduce，它不需要迭代一个结果的所有元素。

在回调内部，搜索值与实际item之间的绝对值为delta，并与上一个增量值进行比较。如果大于或等于，则迭代停止，因为其所有其他值与他们的增量值都大于实际值。

如果回调中的delta较小，则将实际项目分配给结果，delta保存为das lastDelta。

在结果中，采用等于三角形的较小值，如下面的22示例所示，结果为2。

如果有更大的价值的优先级，增量检查必须从

if (delta >= lastDelta) {

改为

if (delta > lastDelta) { 
//  ^^^ without equal sign

这与22得到的，更大的价值的结果42（优先）。

此函数需要数组中的排序值。

function closestValue(array, value) { 
 
    var result, 
 
     lastDelta; 
 

 
    array.some(function (item) { 
 
     var delta = Math.abs(value - item); 
 
     if (delta >= lastDelta) { 
 
      return true; 
 
     } 
 
     result = item; 
 
     lastDelta = delta; 
 
    }); 
 
    return result; 
 
} 
 

 
var data = [2, 42, 82, 122, 162, 202, 242, 282, 322, 362]; 
 

 
console.log(21, closestValue(data, 21)); // 2 
 
console.log(22, closestValue(data, 22)); // 2 smaller value 
 
console.log(23, closestValue(data, 23)); // 42 
 
console.log(80, closestValue(data, 80)); // 82

代码以更大的值

function closestValue(array, value) { 
 
    var result, 
 
     lastDelta; 
 

 
    array.some(function (item) { 
 
     var delta = Math.abs(value - item); 
 
     if (delta > lastDelta) { 
 
      return true; 
 
     } 
 
     result = item; 
 
     lastDelta = delta; 
 
    }); 
 
    return result; 
 
} 
 

 
var data = [2, 42, 82, 122, 162, 202, 242, 282, 322, 362]; 
 

 
console.log(21, closestValue(data, 21)); // 2 
 
console.log(22, closestValue(data, 22)); // 42 greater value 
 
console.log(23, closestValue(data, 23)); // 42 
 
console.log(80, closestValue(data, 80)); // 82

0的优先级：

具有较小值的优先级码

+0

所以你认为给定的数组是排序的...这可以节省你很多时间。 – Redu 2017-01-08 21:45:31

+0

op的数组看起来排序了，所以是的:) – 2017-01-08 22:03:25

答

另一种变型是，我们将头部连接到脚趾的圆形范围内，只接受给定输入的最小值。这帮助我获得了一种加密算法的char代码值。

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

从阵列中获得最接近的数字

对于排序的阵列（线性搜索）

工程与无序阵列

相关推荐