数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学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) {
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 循环重复地将搜索范围减半，直到找到目标值或范围为空。它具有简单的实现方式，并且适用于大多数场景。另一方面，递归方法使用递归函数执行二分查找。它遵循与迭代方法相同的逻辑，但使用函数调用而不是循环。递归二分查找提供了更简洁的实现，但由于函数调用堆栈操作，可能会有稍微更高的开销。总的来说，两种方法都提供了有效且可靠的执行二分查找操作的方式。
更新于：2023年7月28日
1K+ 次浏览
广告