最近的關鍵匹配搜索陣列

Question

是否有更好/更優雅/更有效的方式來做到這一點？

我有一個數組，我在搜索鍵的值，要麼匹配或小於搜索值最大的價值。希望這是有道理的。

我現在的方法是有點蠻力嘗試是罰款數據的小集合，但此功能需要一個大陣多次運行的。

$needle = '2013-04-04';  

$haystack = array (
        '2013-01-01' => 1, 
        '2013-04-03' => 2, 
        '2013-04-05' => 3, 
        '2013-07-23' => 4, 
        '2013-09-12' => 5, 
        '2013-10-18' => 6, 
        '2013-11-01' => 7 
        ); 

krsort($haystack); 

foreach ($haystack as $k => $v) 
    { 
    $possibleMatch = $k; 
    if ($needle >= $k) break; 
    } 

return $possibleMatch 

在此先感謝

Answer 1

看你的數據，它看起來像你的數組進行排序。如果不是這樣，那就用暴力繼續。如果沒有完全匹配，我認爲快速獲得結果的方法是bisection（也稱爲二分搜索或二分法）。僞代碼：

在數組中間取一個鍵。 如果關鍵是不如你的搜索，使用該密鑰 啓動子陣列中搜索如果關鍵是要優於你的搜索，子陣列使用該密鑰 重複結束搜索，直到數組的大小1.

像這樣：

+----------------------------------------------------------------------------------------+ 
    |                      | 
    +----------------------------------------------------------------------------------------+ 
    +----------------------------------------+ +---------------------------------------------+ 
    |          | |            | 
    +----------------------------------------+ +---------------------------------------------+ 
    +------------------+ +-------------------+ 
    |     | |     | 
    +------------------+ +-------------------+ 
         +--------+ +--------+ 
         |  | |  | 
         +--------+ +--------+ 
         +---++---+ 
         | || | 
         +---++---+ 
         +-+ 
         | | 
         +-+ 

         desired value 

警告：切勿，我再說一遍，請勿搜索在谷歌圖片平分。好痛。

Answer 2

使用修改的二進制搜索。一個樣本在這裏 - modify binary search to find the next bigger item than the key;可以輕鬆定製以滿足您的需求。