PHP 中的二分查找
phpserver side programmingprogramming
什么是二分查找?
二分查找是一种搜索算法，用于高效地在已排序的数组(或列表)中查找目标值的位置。它的工作原理是反复将搜索范围一分为二，然后将中间元素与目标值进行比较。
二分查找算法遵循以下步骤:
从整个排序数组开始。
将左指针设置为数组的第一个元素，将右指针设置为最后一个元素。
计算中间索引作为左右指针的平均值(整数除法)。
将中间索引处的值与目标值进行比较。
如果中间值等于目标值，则搜索成功，算法返回索引。
如果目标值大于中间值，则通过将左指针更新为 mid + 1 来消除搜索范围的左半部分。
如果目标值小于中间值，则通过将右指针更新为 mid - 来消除搜索范围的右半部分1.
重复步骤 3 至 7，直到找到目标值或搜索范围为空(左指针大于右指针)。
如果搜索范围为空且未找到目标值，则算法认为目标值不在数组中，并返回 -1 或适当的指示。
二分查找是一种非常有效的算法，时间复杂度为 O(log n)，其中 n 是数组中元素的数量。它对于大型排序数组特别有效，因为它通过在每个步骤中将其分成两半来快速缩小搜索范围，即使元素数量很多也可以快速搜索。
二分查找的 PHP 程序
方法 1- 使用迭代
示例
<?php
function binarySearch($arr, $target) {
$left = 0;
$right = count($arr) - 1;
while ($left <= $right) {
$mid = floor(($left + $right) / 2);
// 检查目标值是否位于中间索引处
if ($arr[$mid] === $target) {
return $mid;
}
// 如果目标值较大，则忽略左半部分
if ($arr[$mid] < $target) {
$left = $mid + 1;
}
// 如果目标值较小，则忽略右半部分
else {
$right = $mid - 1;
}
}
// 数组中未找到目标值
return -1;
}
// 示例用法 1
$sortedArray = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
$targetValue = 91;
$resultIndex = binarySearch($sortedArray, $targetValue);
if ($resultIndex === -1) {
echo "数组中未找到目标值。<br>";
} else {
echo "在索引 $resultIndex 处找到目标值。<br>";
}
// 示例用法 2
$targetValue = 42;
$resultIndex = binarySearch($sortedArray, $targetValue);
if ($resultIndex === -1) {
echo "数组中未找到目标值。";
} else {
echo "在索引 $resultIndex 处找到目标值。";
}
?>
输出
在索引 9 处找到目标值。 在数组中未找到目标值。
方法 2- 使用递归
示例
<?php
function binarySearchRecursive($arr, $target, $left, $right) {
if ($left > $right) {
// 在数组中未找到目标值
return -1;
}
$mid = floor(($left + $right) / 2);
// 检查是否在中间索引处找到目标值
if ($arr[$mid] === $target) {
return $mid;
}
// 如果目标较大，则搜索右半部分
if ($arr[$mid] < $target) {
return binarySearchRecursive($arr, $target, $mid + 1, $right);
}
// 如果目标较小，则搜索左半部分
return binarySearchRecursive($arr, $target, $left, $mid - 1);
}
// 递归二进制搜索的包装函数
function binarySearch($arr, $target) {
$left = 0;
$right = count($arr) - 1;
return binarySearchRecursive($arr, $target, $left, $right);
}
// 示例用法
$sortedArray = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
$targetValue = 16;
$resultIndex = binarySearch($sortedArray, $targetValue);
if ($resultIndex === -1) {
echo "数组中未找到目标值。";
} else {
echo "在索引 $resultIndex 处找到目标值。";
}
?>
输出
在索引 4 处找到目标值。
结论
总之，二分查找是一种功能强大的算法，可以有效地在排序数组中查找目标值。它提供了两种常见的实现方式:迭代和递归。迭代方法使用 while 循环反复将搜索范围一分为二，直到找到目标值或范围变为空。它具有简单的实现方式，非常适合大多数场景。另一方面，递归方法使用递归函数来执行二分查找。它遵循与迭代方法相同的逻辑，但使用函数调用而不是循环。递归二分查找提供了更简洁的实现，但由于函数调用堆栈操作，开销可能会略高。总体而言，这两种方法都提供了高效可靠的二分查找操作方法。
