二分查找(Binary Search)是一種在有序數組中查找目標值的高效算法,其時間復雜度為 O(log n)。在 PHP 中實現二分查找的最佳實踐包括以下幾點:
sort()
函數對數組進行排序。(left + right) / 2
或 (left + right) >> 1
計算中間索引。以下是一個使用循環實現的 PHP 二分查找示例:
function binarySearch($arr, $target) {
$left = 0;
$right = count($arr) - 1;
while ($left <= $right) {
$mid = ($left + $right) >> 1;
if ($arr[$mid] == $target) {
return $mid;
} elseif ($arr[$mid] < $target) {
$left = $mid + 1;
} else {
$right = $mid - 1;
}
}
return -1;
}
在使用二分查找時,還需要注意以下幾點:
+
運算符進行加法操作時,如果兩個整數的和超過了 PHP 中的整數最大值(PHP_INT_MAX),就會發生整數溢出。為了避免這種情況,可以使用位運算符 >>
來代替加法運算符。