PHP 實現二分查找算法（支持升序/降序數組自適應）

二分查找是有序數組中查找目標值的經典 O(log n) 算法。本文提供一個 PHP 實現，自動檢測數組排序方向（升序/降序），並正確處理邊界條件，代碼經實測可靠，適合教學與實際項目參考。

完整代碼實現

<?php
/**
 * 二分查找：判斷有序數組是否包含指定值
 * @param array $array 已排序數組（升序或降序）
 * @param mixed $value 待查找值
 * @return int 1=找到, -1=不存在
 */
function binarySearch(array $array, $value) {
    $max = count($array) - 1;
    $min = 0;
    // 自動判斷排序方向
    $isAsc = $array[$min] < $array[$max];

    while (true) {
        if ($max < $min) return -1; // 搜索區間為空

        // 計算中間索引（向上取整避免死循環）
        $sum = $min + $max;
        $mid = (int)($sum % 2 === 1 ? ceil($sum / 2) : $sum / 2);

        if ($value == $array[$mid]) {
            return 1; // 找到
        } elseif ($value > $array[$mid]) {
            $isAsc ? $min = $mid + 1 : $max = $mid - 1;
        } else { // $value < $array[$mid]
            $isAsc ? $max = $mid - 1 : $min = $mid + 1;
        }
    }
}

// 測試用例
$arr = [4, 5, 7, 8, 9, 10, 11, 12];
$key = 8;

echo "升序數組查找 $key: " . binarySearch($arr, $key) . "\n"; // 1

rsort($arr); // 降序
echo "降序數組查找 $key: " . binarySearch($arr, $key) . "\n"; // 1

echo "查找不存在值 100: " . binarySearch($arr, 100) . "\n"; // -1
?>

關鍵點解析

使用限制與擴展

• 前提條件：數組必須已排序（單調遞增或遞減），且鍵為連續數字索引 0..n-1
• 非連續鍵數組：需先 array_values($arr) 重建索引
• 多值查找：若需返回所有匹配索引，可在找到後向左右擴展掃描
• 泛型比較：當前用 ==，對象/數組比較需傳入自定義比較函數

性能對比

數組長度 1,000,000 時：

• 線性查找 in_array()：~500,000 次比較（平均）
• 二分查找：最多 20 次比較（log₂1,000,000 ≈ 20）

對於靜態有序數據（如字典、郵編、ID 白名單），二分查找是極佳選擇。