PHP 循序查找與二分查找實作比較：演算法原理、程式碼與效能分析

前言

查找是程式設計基礎操作。循序查找 (Linear Search) 適用無序資料，二分查找 (Binary Search) 要求有序但極快。本文以 PHP 類別封裝兩種演算法，並分析時間複雜度與適用場景。

完整類別實作

class SearchDemo {
    private array $data;

    public function __construct(array $data) {
        $this->data = $data;
    }

    // 循序查找 O(n)
    public function linearSearch($val): bool {
        foreach ($this->data as $k => $v) {
            if ($v === $val) {
                echo "循序查找成功: 索引 $k\n";
                return true;
            }
        }
        echo "循序查找失敗\n";
        return false;
    }

    // 二分查找 O(log n) - 需有序陣列
    public function binarySearch($val): bool {
        $arr = $this->data;
        sort($arr, SORT_NUMERIC); // 確保有序
        $low = 0;
        $high = count($arr) - 1;

        while ($low <= $high) {
            $mid = (int)(($low + $high) / 2);
            if ($arr[$mid] === $val) {
                echo "二分查找成功: 排序後索引 $mid\n";
                return true;
            } elseif ($val < $arr[$mid]) {
                $high = $mid - 1;
            } else {
                $low = $mid + 1;
            }
        }
        echo "二分查找失敗\n";
        return false;
    }
}

// 使用
$demo = new SearchDemo([1,2,3,5,7,6,4,8]);
$demo->linearSearch(6);  // 成功
$demo->binarySearch(6);  // 成功 (內部排序後查找)

演算法比較表

關鍵細節：二分查找邊界條件

• while ($low <= $high)：區間為閉區間 [$low, $high]。
• $mid = (int)(($low + $high) / 2)：向下取整，避免溢位 (PHP 整數無上限，但習慣寫法)。
• 縮小區間：$high = $mid - 1 / $low = $mid + 1，確保區間嚴格縮小，避免無限迴圈。

PHP 內建替代方案

// 循序查找鍵值
$key = array_search($val, $arr); // 嚴格模式 array_search($val, $arr, true)

// 二分查找: 內建無直接函數，但可用
// 1. 擴展函數 (需安裝)
// 2. 自行實作或引用庫 (如 php-algorithms)
// 3. 大量查找時，建議先 sort 後用自寫 binarySearch

總結

小資料量用 array_search / 循序查找即可；大資料量、高頻查找務必排序後用二分查找 (或改用雜湊表 isset($map[$val]) 達 O(1))。理解演算法複雜度與資料結構特性，是寫出高效能 PHP 程式的關鍵。