PHP 二分搜尋法實作：支援正序/逆序陣列的高效查找

前言

二分搜尋是有序陣列查找的標準演算法，時間複雜度 O(log n)。本文提供支援遞增（正序）與遞減（逆序）雙模式的 PHP 實作，並修正網路上常見的邊界條件錯誤。

核心實作

<?php
/**
 * 二分搜尋：判斷有序陣列是否包含指定值
 * @param array $array  已排序陣列（遞增或遞減）
 * @param mixed $value  待搜尋值
 * @return int  找到返回 1，未找到返回 -1
 */
function binarySearch(array $array, $value) {
    $min = 0;
    $max = count($array) - 1;

    // 判斷排序方向：首元素 < 尾元素 為遞增
    $isAsc = $array[$min] < $array[$max];

    while (true) {
        if ($max < $min) {
            return -1; // 搜尋區間耗盡
        }

        // 計算中間索引（避免溢位寫法：$min + (($max - $min) >> 1)）
        $mid = $min + (($max - $min) >> 1); // 等同 floor(($min+$max)/2)

        $midVal = $array[$mid];

        if ($value === $midVal) {
            return 1; // 找到
        }

        if ($isAsc) {
            // 遞增：目標較大 -> 搜尋右半；較小 -> 左半
            if ($value > $midVal) {
                $min = $mid + 1;
            } else {
                $max = $mid - 1;
            }
        } else {
            // 遞減：目標較大 -> 搜尋左半；較小 -> 右半
            if ($value > $midVal) {
                $max = $mid - 1;
            } else {
                $min = $mid + 1;
            }
        }
    }
}

// ===== 測試 =====
$asc  = [4, 5, 7, 8, 9, 10, 11, 12];
$desc = [12, 11, 10, 9, 8, 7, 5, 4]; // rsort($asc)

$testValues = [4, 7, 12, 13, 3];

echo "遞增陣列:\n";
foreach ($testValues as $v) {
    echo "搜尋 $v : " . (binarySearch($asc, $v) === 1 ? '找到' : '未找到') . "\n";
}

echo "\n遞減陣列:\n";
foreach ($testValues as $v) {
    echo "搜尋 $v : " . (binarySearch($desc, $v) === 1 ? '找到' : '未找到') . "\n";
}

關鍵點解析

1. 排序方向自動偵測： $array[0] < $array[$max] 一次比較即可，無需額外參數。
2. 中間索引計算： 使用 $min + (($max - $min) >> 1) 避免整數溢位（PHP 整數通常不溢位，但此寫法為通用最佳實踐）。
3. 邊界收斂： $min = $mid + 1 / $max = $mid - 1 確保區間嚴格縮小，避免無限迴圈。
4. 嚴格比較 ===： 確保型別一致（如 "5" !== 5），若需寬鬆比較可改 ==。
5. 回傳值語義： 1=存在, -1=不存在。若需索引可改回傳 $mid 或 false。

適用場景與限制

• ✅ 適用：靜態有序陣列、整數/浮點數/字串（字典序）查找。
• ❌ 不適用：關聯陣列（非連續索引）、未排序資料、頻繁插入/刪除的動態集合（改用 BST、Hash Table）。
• ⚠️ 陣列鍵必須為連續整數 0..n-1，否則需先 array_values() 重建索引。

效能對比

$arr = range(1, 1000000); // 100 萬元素
$target = 999999;

$t1 = microtime(true);
$found = in_array($target, $arr); // O(n) 線性搜尋
$t2 = microtime(true);
echo "in_array: " . ($t2-$t1)*1000 . " ms\n";

$t1 = microtime(true);
$found = binarySearch($arr, $target); // O(log n)
$t2 = microtime(true);
echo "binarySearch: " . ($t2-$t1)*1000 . " ms\n";

// 輸出範例：
// in_array: 12.5 ms
// binarySearch: 0.02 ms

資料量越大，二分搜尋優勢越明顯。

結語

二分搜尋是演算法面試必考、實務高頻工具。掌握邊界條件正確收斂、排序方向自適應、避免溢位中間值計算三要素，即可寫出正確、高效、可複用的搜尋函式。