尋找高效算法在整數列表中尋找最接近的整數

這是情況。我有一個整數列表，表示需要在某個毫秒內觸發的事件。這份名單看起來像：尋找高效算法在整數列表中尋找最接近的整數

然後我有一個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

尋找高效算法在整數列表中尋找最接近的整數

回答

相關問題