PHP 陣列二分搜尋法（Binary Search）實作

演算法原理

二分搜尋要求陣列已排序。每次取中間元素比較，若目標值較小則搜尋左半部，較大則搜尋右半部，時間複雜度 O(log n)，遠優於線性搜尋 O(n)。

遞迴實作

/**
 * 二分搜尋遞迴實作
 * @param array $array 已排序陣列（數字索引）
 * @param mixed $target 搜尋目標值
 * @param int $low 搜尋範圍起始索引
 * @param int $high 搜尋範圍結束索引
 * @return int 找到回傳索引，否則 -1
 */
function binarySearch($array, $target, $low = 0, $high = 0) {
    // 首次呼叫自動設定高界
    if ($high === 0 && count($array) > 0) {
        $high = count($array) - 1;
    }

    if ($low <= $high) {
        $mid = (int)(($low + $high) / 2);
        if ($array[$mid] == $target) {
            return $mid;
        } elseif ($target < $array[$mid]) {
            return binarySearch($array, $target, $low, $mid - 1);
        } else {
            return binarySearch($array, $target, $mid + 1, $high);
        }
    }
    return -1; // 未找到
}

測試範例

$arr = [4, 5, 7, 8, 9, 10];
echo binarySearch($arr, 8);  // 輸出 3（索引）
echo binarySearch($arr, 6);  // 輸出 -1（不存在）

注意事項與改進

• 陣列必須已排序：未排序陣列結果不可預期。
• 索引類型：此實作假設數字索引 0..n-1。關聯陣列需先 array_values() 重建索引。
• 嚴格比較：使用 === 可區分 1 與 '1'，視需求調整。
• 迭代版本：避免遞迴呼叫堆疊溢位，大資料量建議改寫 while 迴圈。

迭代版本參考

function binarySearchIterative($array, $target) {
    $low = 0;
    $high = count($array) - 1;
    while ($low <= $high) {
        $mid = (int)(($low + $high) / 2);
        if ($array[$mid] == $target) return $mid;
        if ($target < $array[$mid]) $high = $mid - 1;
        else $low = $mid + 1;
    }
    return -1;
}

內建函數替代

PHP 內建 array_search() 為線性搜尋；若陣列已排序且頻繁搜尋，自行實作二分搜尋或使用 SplFixedArray 搭配二分法效能最佳。