PHP 實作循序搜尋與二分搜尋演算法

搜尋演算法比較

1. 循序搜尋 (Linear Search)

<?php
/**
 * 循序搜尋
 * @param array $arr 搜尋陣列
 * @param mixed $target 目標值
 * @return int|false 找到返回索引，否則 false
 */
function linearSearch(array $arr, $target)
{
    foreach ($arr as $index => $value) {
        if ($value === $target) {
            return $index;
        }
    }
    return false;
}

// 測試
$data = [1, 2, 3, 5, 7, 6, 4, 8];
var_dump(linearSearch($data, 5));  // int(3)
var_dump(linearSearch($data, 9));  // bool(false)
?>

2. 二分搜尋 (Binary Search) - 迭代版

<?php
/**
 * 二分搜尋 (迭代實作)
 * @param array $arr **已排序** 陣列
 * @param mixed $target 目標值
 * @return int|false 找到返回索引，否則 false
 */
function binarySearch(array $arr, $target)
{
    $low = 0;
    $high = count($arr) - 1;
    
    while ($low <= $high) {
        $mid = (int)(($low + $high) / 2);
        $midVal = $arr[$mid];
        
        if ($midVal === $target) {
            return $mid;
        } elseif ($midVal < $target) {
            $low = $mid + 1;
        } else {
            $high = $mid - 1;
        }
    }
    return false;
}

// 測試 (資料必須先排序)
$sortedData = [1, 2, 3, 4, 5, 6, 7, 8];
var_dump(binarySearch($sortedData, 5)); // int(4)
var_dump(binarySearch($sortedData, 9)); // bool(false)
?>

3. 二分搜尋 - 遞迴版

<?php
function binarySearchRecursive(array $arr, $target, int $low = 0, int $high = null)
{
    if ($high === null) $high = count($arr) - 1;
    if ($low > $high) return false;
    
    $mid = (int)(($low + $high) / 2);
    
    if ($arr[$mid] === $target) return $mid;
    if ($arr[$mid] < $target) return binarySearchRecursive($arr, $target, $mid + 1, $high);
    return binarySearchRecursive($arr, $target, $low, $mid - 1);
}
?>

4. PHP 內建函數替代

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

// array_search - 循序搜尋 (嚴格模式)
$key = array_search(5, $arr, true); // 4

// 在有序陣列二分搜尋無內建函數，但可用二分查找庫或自行實作

// 陣列去重 + 排序 + 搜尋組合
$uniqueSorted = array_values(array_unique($arr));
sort($uniqueSorted);
?>

5. 效能實測 (100萬筆資料)

<?php
$data = range(1, 1_000_000);
$target = 999_999;

$start = microtime(true);
linearSearch($data, $target);
echo "循序搜尋: " . (microtime(true) - $start) . " 秒\n"; // ~0.03s

$start = microtime(true);
binarySearch($data, $target);
echo "二分搜尋: " . (microtime(true) - $start) . " 秒\n"; // ~0.00001s
?>

6. 實務建議

• 資料量 < 50：循序搜尋足夠，程式碼簡單
• 頻繁搜尋大量資料：維護有序陣列 + 二分搜尋，或改用資料庫索引
• 關聯式搜尋：使用雜湊表 (PHP 陣列鍵值) O(1) 查找 $map[$key]
• 複雜條件：資料庫 WHERE 條件 + 索引優化

選對演算法，是效能優化的第一步。