什么是二分查找？

二分搜索是一种搜索算法，用于有效地查找排序数组（或列表）中目标值的位置。它的工作原理是重复将搜索范围一分为二，并将中间元素与目标值进行比较。

二分查找算法遵循以下步骤：

• 从整个排序数组开始。

• 将左指针设置为数组的第一个元素，将右指针设置为最后一个元素。

• 计算中间索引作为左右指针的平均值（整数除法）。

• 将中间索引处的值与目标值进行比较。

• 如果中间值等于目标值，则搜索成功，算法返回索引。

• 如果目标值大于中间值，则通过将左指针更新为 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);
      // Check if the target value is found at the middle index
      if ($arr[$mid] === $target) {
         return $mid;
      }
      // If the target is greater, ignore the left half
      if ($arr[$mid] < $target) {
         $left = $mid + 1;
      }
      // If the target is smaller, ignore the right half
      else {
         $right = $mid - 1;
      }
   }
   // Target value not found in the array
   return -1;
}
// Example usage 1
$sortedArray = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
$targetValue = 91;
$resultIndex = binarySearch($sortedArray, $targetValue);
if ($resultIndex === -1) {
   echo "Target value not found in the array.<br>";
} else {
   echo "Target value found at index $resultIndex.<br>";
}
// Example usage 2
$targetValue = 42;
$resultIndex = binarySearch($sortedArray, $targetValue);
if ($resultIndex === -1) {
   echo "Target value not found in the array.";
} else {
   echo "Target value found at index $resultIndex.";
}
?>

输出

Target value found at index 9.
Target value not found in the array.

方法 2 - 使用递归

示例

<?php
function binarySearchRecursive($arr, $target, $left, $right) {
   if ($left > $right) {
      // Target value not found in the array
      return -1;
   }
   $mid = floor(($left + $right) / 2);
   // Check if the target value is found at the middle index
   if ($arr[$mid] === $target) {
      return $mid;
   }
   // If the target is greater, search the right half
   if ($arr[$mid] < $target) {
      return binarySearchRecursive($arr, $target, $mid + 1, $right);
   }
   // If the target is smaller, search the left half
   return binarySearchRecursive($arr, $target, $left, $mid - 1);
}
// Wrapper function for the recursive binary search
function binarySearch($arr, $target) {
   $left = 0;
   $right = count($arr) - 1;
   return binarySearchRecursive($arr, $target, $left, $right);
}
// Example usage
$sortedArray = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
$targetValue = 16;
$resultIndex = binarySearch($sortedArray, $targetValue);
if ($resultIndex === -1) {
   echo "Target value not found in the array.";
} else {
   echo "Target value found at index $resultIndex.";
}
?>

输出

Target value found at index 4.

结论

总之，二分搜索是一种强大的算法，可以在排序数组中有效地查找目标值。它提供了两种常见的实现：迭代和递归。迭代方法使用 while 循环重复将搜索范围一分为二，直到找到目标值或范围变空。它具有简单的实现方式，非常适合大多数场景。另一方面，递归方法采用递归函数来执行二分搜索。它遵循与迭代方法相同的逻辑，但使用函数调用而不是循环。递归二分搜索提供了更简洁的实现，但由于函数调用堆栈操作可能具有稍高的开销。总的来说，这两种方法都提供了执行二分搜索操作的高效可靠的方法。