当前位置：首页 > article >正文

PHP 二分法查找算法

article 2024/11/24 14:51:47

二分法查找算法（Binary Search），也被称为折半查找，是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是目标值，则搜索过程结束；如果目标值大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。

以下是一个用PHP实现的二分法查找算法的示例代码：

<?php
function binarySearch($array, $target) {
    $low = 0;
    $high = count($array) - 1;

    while ($low <= $high) {
        $mid = intdiv($low + $high, 2); // 使用intdiv确保结果为整数

        // 检查中间元素是否是目标值
        if ($array[$mid] == $target) {
            return $mid; // 找到目标值，返回其索引
        }

        // 如果目标值大于中间元素，则在右半部分继续查找
        if ($array[$mid] < $target) {
            $low = $mid + 1;
        } else { // 如果目标值小于中间元素，则在左半部分继续查找
            $high = $mid - 1;
        }
    }

    // 如果未找到目标值，则返回-1
    return -1;
}

// 测试二分法查找
$array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
$target = 7;

$result = binarySearch($array, $target);

if ($result != -1) {
    echo "元素 $target 在数组中的索引为: $result\n";
} else {
    echo "元素 $target 不在数组中\n";
}
?>

代码解释：

函数定义：
- function binarySearch($array, $target)：定义一个名为binarySearch的函数，接受两个参数，一个是有序数组$array，另一个是目标值$target。
初始化变量：
- $low = 0：初始化最低索引为0。
- $high = count($array) - 1：初始化最高索引为数组最后一个元素的索引。
循环查找：
- while ($low <= $high)：当最低索引不大于最高索引时，继续查找。
- $mid = intdiv($low + $high, 2)：计算中间索引，使用intdiv函数确保结果为整数。
- 检查中间元素是否是目标值，如果是则返回其索引。
- 如果目标值大于中间元素，则更新最低索引为$mid + 1，在右半部分继续查找。
- 如果目标值小于中间元素，则更新最高索引为$mid - 1，在左半部分继续查找。
返回结果：
- 如果找到目标值，则返回其索引。
- 如果未找到目标值，则返回-1。
测试：
- 定义一个有序数组$array和目标值$target。
- 调用binarySearch($array, $target)函数进行查找。
- 根据返回结果输出相应的信息。