PHP 二分查找雙重實現：遞歸與迭代版本、插值優化中值選取策略

二分查找要求有序陣列，核心在於中值選取與區間縮減。本文提供遞歸與迭代雙版本，並引入插值法在均勻分布數據下將複雜度從 O(log n) 降至 O(log log n)。

核心輔助：中值選取函數

/**
 * 選取中值索引
 * @param array $subject 有序陣列
 * @param int $low 下界
 * @param int $high 上界
 * @param mixed $key 目標值（插值法需用）
 * @return int
 */
function getMidKey(array $subject, int $low, int $high, $key): int {
    // 方案 1：標準中值（防溢出寫法）
    // return (int)($low + ($high - $low) / 2);

    // 方案 2：插值法（數據均勻分布時極快）
    // 公式：low + (key - arr[low]) / (arr[high] - arr[low]) * (high - low)
    if ($subject[$high] == $subject[$low]) return (int)(($low + $high) / 2); // 避免除零
    return (int)round(
        $low + (($key - $subject[$low]) / ($subject[$high] - $subject[$low])) * ($high - $low)
    );
}

版本一：遞歸實現

function binarySearch_r(array $subject, int $start, int $end, $key) {
    if ($start >= $end) return false;
    $mid = getMidKey($subject, $start, $end, $key);
    if ($subject[$mid] == $key) return $mid;
    if ($key > $subject[$mid]) {
        return binarySearch_r($subject, $mid + 1, $end, $key); // 注意 +1 避免死循環
    }
    return binarySearch_r($subject, $start, $mid - 1, $key);   // 注意 -1
}

版本二：迭代實現（推薦生產）

function binarySearch_nr(array $subject, int $n, $key) {
    $low = 0;
    $high = $n - 1; // 最後有效索引
    while ($low <= $high) {
        $mid = getMidKey($subject, $low, $high, $key);
        if ($subject[$mid] == $key) return $mid;
        if ($subject[$mid] < $key) {
            $low = $mid + 1;
        } else {
            $high = $mid - 1;
        }
    }
    return false; // 未找到
}

測試驗證

$arr = range(10, 1000, 10); // [10,20,30,...,1000] 均勻分布
$target = 450;

echo "遞歸：" . (binarySearch_r($arr, 0, count($arr)-1, $target) ?: '未找到') . "<br>";
echo "迭代：" . (binarySearch_nr($arr, count($arr), $target) ?: '未找到') . "<br>";
// 均輸出 44 (0-based 索引，值 450)

插值法適用性分析

工程化增強清單

• 邊界檢查：$low < 0 || $high >= count($arr) 拋異常或返回 false。
• 型別一致性：嚴格模式下確保 $key 與陣列元素型別一致（=== 比較）。
• 返回值規範：找到返回 int 索引，未找到返回 false 或 -1，勿混用 null。
• 大數據分頁：結合 LIMIT offset, count 的 SQL 查詢，避免將百萬行載入記憶體再二分。
• 泛型支援：PHP 8.1+ 可用 function binarySearch(array $subject, mixed $key): int|false 簽名。

擴展：查找區間邊界（Lower/Upper Bound）

// 找第一個 >= key 的位置 (lower_bound)
function lowerBound(array $arr, $key): int {
    $low = 0; $high = count($arr);
    while ($low < $high) {
        $mid = (int)(($low + $high) / 2);
        if ($arr[$mid] < $key) $low = $mid + 1;
        else $high = $mid;
    }
    return $low;
}

// 找第一個 > key 的位置 (upper_bound)
function upperBound(array $arr, $key): int {
    $low = 0; $high = count($arr);
    while ($low < $high) {
        $mid = (int)(($low + $high) / 2);
        if ($arr[$mid] <= $key) $low = $mid + 1;
        else $high = $mid;
    }
    return $low;
}

掌握遞歸與迭代雙版本、理解插值法適用邊界、會寫 Lower/Upper Bound，即掌握了有序數據查找的核心工程能力。