最近的关键匹配搜索阵列

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;可以轻松定制以满足您的需求。