PHP 二分搜索

什么是二分搜索

二分搜索是一种在有序数组（或列表）中高效地查找目标值位置的搜索算法。它通过不断将搜索范围划分为两半并将中间元素与目标值比较来工作。

二分搜索算法遵循以下步骤：

• 从整个有序数组开始。

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

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

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

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

• 如果目标值大于中间值，则通过将左指针更新为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) {
         returnmid;
      }
      // 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 1sortedArray = [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 indexresultIndex.<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 indexresultIndex.";
}
?>

输出

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 usagesortedArray = [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 indexresultIndex.";
}
?>

输出

Target value found at index 4.

结论

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