PHP中根据随机数匹配数组区间键值的高效实现方法

嘿，这个场景我之前也碰到过，当数组元素少的时候遍历凑合用，但元素多了效率就跟不上了。咱们可以用排序+二分查找的方案，把时间复杂度从遍历的O(n)降到查询时的O(logn)，完美适配大数据量的情况！

先理清楚需求规则 #

先把你的需求再明确一遍，避免理解偏差：

• 给定的$date数组键是非连续的数值（比如100、93、65）
• 随机数 ≤ 最小键 → 返回空
• 随机数 > 最大键 → 返回最大键对应的元素
• 随机数在两个相邻键之间（比如67在65和93之间）→ 返回较小的那个键的元素

实现步骤&代码示例 #

1. 预处理：提取键并排序 #

首先我们需要把$date的键提取出来，做一次升序排序——这一步只需要执行一次（如果$date数组不会频繁修改的话），后面所有查询都可以复用这个排序后的键数组。

// 你的原始数组
$date = [
    100 => ['card' => 5244, 'start_date' => '2019-05-03 00:00:00'],
    93 => ['card' => 9526, 'start_date' => '2019-05-20 00:00:00'],
    65 => ['card' => 1537, 'start_date' => '2019-07-09 00:00:00'],
    // 更多元素...
];

// 提取键并升序排序
$keys = array_keys($date);
sort($keys);

2. 二分查找匹配键 #

写一个二分查找函数，快速定位到符合条件的键。二分查找的核心是利用有序数组的特性，每次把查找范围缩小一半，效率极高。

function findMatchingKey(array $keys, int $num): ?int {
    $low = 0;
    $high = count($keys) - 1;
    $targetIndex = -1;

    // 二分查找第一个大于$num的键的索引
    while ($low <= $high) {
        $mid = floor(($low + $high) / 2);
        if ($keys[$mid] > $num) {
            $targetIndex = $mid;
            $high = $mid - 1; // 继续向左找，确保找到的是第一个大于$num的键
        } else {
            $low = $mid + 1;
        }
    }

    // 根据索引判断返回结果
    if ($targetIndex === 0) {
        // $num小于等于最小键，返回null
        return null;
    } elseif ($targetIndex === -1) {
        // $num大于所有键，返回最大的键
        return end($keys);
    } else {
        // 返回第一个大于$num的键的前一个键（也就是符合区间的键）
        return $keys[$targetIndex - 1];
    }
}

3. 测试验证 #

用你的测试案例跑一遍，看看结果是否符合预期：

// 测试随机数
$testNumbers = [1, 34, 67, 120];

foreach ($testNumbers as $num) {
    $matchingKey = findMatchingKey($keys, $num);
    $result = $matchingKey !== null ? $date[$matchingKey] : null;
    
    echo "随机数 {$num} 的匹配结果：\n";
    var_dump($result);
    echo "-------------------------\n";
}

输出结果：

随机数 1 的匹配结果：
NULL
-------------------------
随机数 34 的匹配结果：
NULL
-------------------------
随机数 67 的匹配结果：
array(2) {
  ["card"]=>
  int(1537)
  ["start_date"]=>
  string(19) "2019-07-09 00:00:00"
}
-------------------------
随机数 120 的匹配结果：
array(2) {
  ["card"]=>
  int(5244)
  ["start_date"]=>
  string(19) "2019-05-03 00:00:00"
}

完全符合你的需求！

为什么这个方法高效？ #

• 预处理阶段：排序的时间复杂度是O(nlogn)，但只需要执行一次。
• 查询阶段：每次二分查找的时间复杂度是O(logn)，哪怕数组有10000个元素，最多也只需要14次比较，比遍历所有元素快太多。

额外注意点 #

• 如果$date数组是空的，记得在函数里加个判断，直接返回null即可。
• 如果键可能有重复（虽然问题里没提到），可以在排序后去重，避免影响匹配逻辑。

内容的提问来源于stack exchange，提问作者Fresh Lover