close

PHP 中的二分查找 (Binary Search) 算法：说明、步骤和示例

二分查找算法是在排序数组中查找特定值的有效方法。 这种方法将数组分成更小的部分，并不断将搜索范围中间位置的值与目标值进行比较。 如果值匹配，则找到所需的值； 否则，算法继续缩小搜索范围并重复该过程，直到找到该值或没有更多元素可供检查。

脚步：

  1. 初始化搜索范围： 首先选择从  数组的第一个位置 left  到最后一个位置的搜索范围。 right
  2. 求中点： left 通过对左右位置 求平均来计算中点； 这是搜索范围的中间点。
  3. 比较值： 将中间点的值与目标值进行比较。
  4. 处理比较结果： 如果中间点的值与目标值匹配，则返回该位置。 如果中间点的值小于目标值，则将左侧位置更新为middle + 1以搜索右半部分。 如果中间点的值大于目标值，则将右侧位置更新为 middle- 1 以搜索左半部分。
  5. 重复： 重复步骤2到4，直到找到该值或没有更多元素可供检查 left > right。

的优点和缺点

优点：

  • 高效的性能： 该算法的时间复杂度为O(log n)，对于处理大型数据集非常高效。
  • 对大型数据集有效： 二分搜索可有效减少大型数据集快速检查的元素数量。

缺点：

  • 仅适用于排序数组： 该算法仅适用于排序数组。
  • 可变步数： 查找值所需的步数取决于其在数组中的位置，对于靠近末尾的值可能需要很多步。

示例：在 PHP 中的排序数组中查找值 12 的二分查找 

function binarySearch($arr, $target) {  
    $left = 0;  
    $right = count($arr)- 1;  
  
    while($left <= $right) {  
        $mid = floor(($left + $right) / 2);  
  
        if($arr[$mid] == $target) {  
            return $mid; // Return the position of the value  
        } elseif($arr[$mid] < $target) {  
            $left = $mid + 1;  
        } else {  
            $right = $mid- 1;  
        }  
    }  
  
    return -1; // Value not found  
}  
  
$array = [2, 5, 8, 12, 15, 20, 30];  
$targetValue = 12;  
  
$result = binarySearch($array, $targetValue);  
  
if($result != -1) {  
    echo "Value $targetValue found at position $result.";  
} else {  
    echo "Value $targetValue not found in the array.";  
}

示例说明

  1.  我们从数组的第一个位置 left = 0 到最后一个位置的 初始搜索范围开始。 right = 6
  2. 我们通过左右位置的平均来计算中间点（mid）； mid = 3。 中间的值为 12。
  3. 我们将) 处的值 mid(12 与目标值(12) 进行比较并找到匹配项，因此我们返回位置 3。
  4. 算法结束，我们输出结果“在位置 3 找到值 12”。