萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> PHP 程式設計

PHP 二分查找算法實現:兼容升序/降序數組、邊界條件全覆蓋

算法原理

二分查找要求數組已排序(升序或降序)。每次取中間元素與目標值比較,根據大小關係丟棄一半搜索空間,時間複雜度 O(log n)。

通用實現(自動識別排序方向)

<?php
/**
 * 二分查找:判斷有序數組是否包含目標值
 * @param array $array  已排序數組(升序或降序)
 * @param mixed $value  目標值
 * @return int          1=找到, -1=不存在
 */
function binarySearch(array $array, $value): int {
    $min = 0;
    $max = count($array) - 1;
    if ($max < 0) return -1; // 空數組
    
    // 自動檢測排序方向
    $isAsc = $array[$min] < $array[$max];
    
    while ($min <= $max) {
        // 防止整數溢出(PHP 整數無上限,但習慣寫法)
        $mid = $min + (($max - $min) >> 1); // 等同 floor(($min + $max) / 2)
        $midVal = $array[$mid];
        
        if ($midVal === $value) {
            return 1; // 找到
        }
        
        if ($isAsc) {
            if ($value > $midVal) {
                $min = $mid + 1;
            } else {
                $max = $mid - 1;
            }
        } else { // 降序
            if ($value < $midVal) {
                $min = $mid + 1;
            } else {
                $max = $mid - 1;
            }
        }
    }
    return -1; // 未找到
}

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

$target = 10;
echo "升序查找 $target: " . binarySearch($asc, $target) . "\n";   // 1
echo "降序查找 $target: " . binarySearch($desc, $target) . "\n"; // 1

echo "升序查找 6: " . binarySearch($asc, 6) . "\n";   // -1
echo "降序查找 6: " . binarySearch($desc, 6) . "\n"; // -1

進階版:返回索引位置(支持插入位置)

<?php
/**
 * 二分查找返回索引
 * @return int 找到返回索引(0-based),未找到返回 ~插入位置 (bitwise complement)
 *             如返回 -3 表示應插入索引 2 保持有序
 */
function binarySearchIndex(array $array, $value): int {
    $low = 0;
    $high = count($array) - 1;
    $isAsc = $array[$low] < $array[$high];
    
    while ($low <= $high) {
        $mid = $low + (($high - $low) >> 1);
        $cmp = $isAsc 
            ? ($value <=> $array[$mid])  // PHP 7+ 太空船操作符
            : ($array[$mid] <=> $value); // 降序反向比較
        
        if ($cmp === 0) return $mid;
        if ($cmp > 0) $low = $mid + 1;
        else $high = $mid - 1;
    }
    return ~$low; // 未找到,返回按位取反的插入位置
}

// 使用
$arr = [10, 20, 30, 40, 50];
$idx = binarySearchIndex($arr, 30); // 2
$idx = binarySearchIndex($arr, 35); // ~3 = -4 (應插入索引 3)
if ($idx < 0) $insertPos = ~$idx;   // 取反得到插入位置

PHP 內置函數對比

函數適用類型返回值性能備註
in_array()任意數組boolO(n)線性掃描,小數組可用
array_search()任意數組key/falseO(n)返回鍵名
isset($arr[$key])關聯數組(鍵查找)boolO(1)哈希表查找,最快
自定義二分查找有序索引數組自定義O(log n)大數組、數值範圍查找

避坑指南

  1. 數組必須有序: 無序數組直接二分查找結果不可預期。先 sort() 或 rsort()。
  2. 非連續鍵名: array_values() 重建 0-based 索引後再查找。
  3. 浮點數比較: 避免直接 ===,用 abs($a - $b) < 0.0001 或 bccomp。
  4. 大數據量: PHP 數組是有序哈希表,內存開銷大。百萬級以上建議用 Redis Sorted Set / MySQL 索引 / Elasticsearch。

實戰場景:分頁定位、區間統計

// 已排序的時間戳數組,查找某時間範圍的起始索引
$timestamps = [1704067200, 1704153600, 1704240000, ...]; // 每天 0點 時間戳
$start = binarySearchIndex($timestamps, strtotime('2024-01-01'));
$end   = binarySearchIndex($timestamps, strtotime('2024-01-31'));
if ($start < 0) $start = ~$start;
if ($end < 0) $end = ~$end - 1; // 最後一個 <= 目標值
$count = max(0, $end - $start + 1);
copyright © 萬盛學電腦網 all rights reserved