寻找高效算法在整数列表中寻找最接近的整数

这是情况。我有一个整数列表，表示需要在某个毫秒内触发的事件。这份名单看起来像：寻找高效算法在整数列表中寻找最接近的整数

然后我有一个playhead通常前进每100ms，但可随机寻道和磨砂前后为好。那个播放头不能保证是100的倍数，但是可以在没有任何实际问题的情况下播放。

我的挑战是如何能够有效地在列表中找到最接近的元素小于或等于当前播放头。列表的平均长度在300到1500个元素之间。我可以很容易地在设定的时间间隔内对前进进行优化，但随机查找稍微复杂一些。

让我希望我不会睡在算法类。

来源

2012-02-08 turing1

最简单的方法：向后循环数组，并选取小于或等于播放头的第一个元素。你有没有试过，这对你的用例来说效率太低了吗？ – deceze 2012-02-08 07:28:25

挑战是*有效*找到...线性搜索效率不高。 – 2012-02-08 07:31:05

尽管如此，它可能很有效*。对于现代机器来说，1500个元素不是那么重要。 – deceze 2012-02-08 07:32:48

我觉得Divide and conquer algorithm是最好的西装。

来源

2012-02-08 07:27:46

这听起来像你想要一个修改的二进制搜索。由于列表按排序顺序排列，二进制搜索将极大地提高线性搜索的搜索性能，并且如果对数组中项目的间距不了解，则无法比二分查找做得更好。二分法搜索将需要稍微修改，因为您不是在寻求平等，而是在没有超过的情况下尽可能接近。

下面是一个实际的算法，保持分割的搜索数据以1/2，直到它下降到仅一个元件（与上半部分或下半部分基于比较将测试值每次去）：

var testData = [0,1500,5000,9348,89234,109280,109281,109283,150000]; 

function findNearest(data, val) { 
    if (!data || !data.length) { 
     return(null); 
    } 
    var lowest = 0, mid; 
    var highest = data.length - 1; 
    while (true) {  
     if (lowest == highest) { 
      return(lowest); 
     } 
     mid = Math.ceil(((highest - lowest)/2) + lowest); 
     if (data[mid] == val) { 
      return(mid); 
     } 
     else if (data[mid] < val) { 
      lowest = mid; 
     } else { 
      highest = Math.max(lowest, mid - 1); 
     } 
    } 
}

而且，工作测试程序：http://jsfiddle.net/jfriend00/rWk2X/

注：此代码假设阵列中的所有值都在有序和数组不为空。

如果给它一个没有小于目标值的值的数组，它将返回0，这可能是一种特殊情况，需要处理，除非确定数组中的第一个值总是小于目标值值（例如总是零）。

如果你给它具有比目标值高出不值的数组，它会在数组中返回的最后一个值（因为它应该），这是不是一个特例，只是所需的答案。

来源

2012-02-08 07:28:41 jfriend00

由于这看起来像一个有趣的算法问题，我在我的答案中增加了一个有效的代码示例。如果你玩这个，小心，因为它很容易得到一个无限循环。实际上，我在测试过程中将最大迭代次数编码到我的代码中（它会在1000次迭代后中止并出错），以避免无限循环。 – jfriend00 2012-02-08 08:01:24

这看起来像是最好的解决方案。是否有一组特定的输入会导致无限循环？ – turing1 2012-02-08 09:21:57

@ turing1 - 输入不会导致无限循环。您可以传入任何内容，并且在代码尝试解释后的注释中处理得很好。只有当你弄乱了函数中的代码并将其加入时，你才会面临无限循环的风险。 – jfriend00 2012-02-08 09:28:34

由于它是一个排序列表，因此使用二分查找。你可以做得更好，但是你必须做出额外的假设（例如，你必须假设数字的分布，我认为不是这种情况）。你可以在这里读到它：http://en.wikipedia.org/wiki/Binary_search_algorithm

来源

2012-02-08 07:30:07

我前一段时间所面临这一问题，取得了一定的执行时间比较。

看看here。（样品不与IE工程）

第四实施似乎真的规则相比，哑二进制搜索。

希望它有帮助。

再见

来源

2012-12-19 10:59:56 fedeghe

寻找高效算法在整数列表中寻找最接近的整数

回答

相关问题