二分查找要求數組已排序(升序或降序)。每次取中間元素與目標值比較,根據大小關係丟棄一半搜索空間,時間複雜度 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; // 取反得到插入位置
| 函數 | 適用類型 | 返回值 | 性能 | 備註 |
|---|---|---|---|---|
in_array() | 任意數組 | bool | O(n) | 線性掃描,小數組可用 |
array_search() | 任意數組 | key/false | O(n) | 返回鍵名 |
isset($arr[$key]) | 關聯數組(鍵查找) | bool | O(1) | 哈希表查找,最快 |
| 自定義二分查找 | 有序索引數組 | 自定義 | O(log n) | 大數組、數值範圍查找 |
sort() 或 rsort()。array_values() 重建 0-based 索引後再查找。===,用 abs($a - $b) < 0.0001 或 bccomp。// 已排序的時間戳數組,查找某時間範圍的起始索引
$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);