PHP 實現順序查找與二分查找算法演示

算法簡介

• 順序查找：從頭遍歷陣列，時間複雜度 O(n)，適用於無序、小規模數據。
• 二分查找：要求陣列已排序，每次折半縮小範圍，時間複雜度 O(log n)，適合大規模有序數據。

封裝類實現

<?php
class Search {
    private $data = [];

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

    /** 順序查找：返回索引或 false */
    public function linear($target) {
        foreach ($this->data as $index => $value) {
            if ($value === $target) {
                return $index;
            }
        }
        return false;
    }

    /** 二分查找：內部自動排序副本，返回索引或 false */
    public function binary($target) {
        $arr = $this->data;
        sort($arr); // 確保有序，原陣列不變
        
        $low = 0;
        $high = count($arr) - 1;
        
        while ($low <= $high) {
            $mid = (int)(($low + $high) / 2);
            if ($arr[$mid] === $target) {
                return $mid; // 返回排序後索引
            } elseif ($target < $arr[$mid]) {
                $high = $mid - 1;
            } else {
                $low = $mid + 1;
            }
        }
        return false;
    }
}

// 測試
$search = new Search([1, 2, 3, 5, 7, 6, 4, 8]);
var_dump($search->linear(5));  // int(3)
var_dump($search->binary(5));  // int(4) (排序後索引)
?>

關鍵點解析

1. 二分查找前必須排序：示例中用 sort($arr) 副本，避免污染原數據。
2. 邊界條件：$low <= $high 而非 <，確保單元素陣列也能查找。
3. 中間索引計算：($low + $high) >> 1 或 intdiv($low + $high, 2) 防溢出（PHP 整數無溢出風險）。
4. 返回值語義：順序查找返回原始索引；二分查找返回排序後索引。實際業務常需返回「原始位置」或「關聯數據」，可改為存儲 [value => original_index] 映射。

內建函數替代方案

<?php
$arr = [1, 2, 3, 5, 7, 6, 4, 8];

// 順序查找：array_search (嚴格模式)
$idx = array_search(5, $arr, true); // 3

// 二分查找：無直接內建，但可用
sort($arr);
$idx = array_search(5, $arr, true); // 4 (排序後)

// 檢查是否存在：in_array / isset($flip[$val])
$exists = in_array(5, $arr, true);

// 大數據集存在性判斷：翻轉鍵值 O(1)
$flip = array_flip($arr);
isset($flip[5]); // true
?>

實際工程建議

• PHP 陣列底層是有序哈希表，isset($arr[$key]) / in_array 已高度優化，百萬級數據仍在毫秒級。
• 頻繁查找、範圍查詢、排序需求 → 改用 資料庫索引 (B+樹)、Redis Sorted Set、Elasticsearch。
• 純算法練習/教學/嵌入式環境 → 手寫二分查找理解邏輯。