php 数组二分法查找函数代码

沃梦达教程 php开发

2023-12-18 7

PHP中数组二分法查找函数代码：

PHP中数组二分法查找函数代码：

function binary_search($arr, $key) {
    $low = 0;
    $high = count($arr) - 1;

    while ($low <= $high) {
        $mid = intval(($low + $high) / 2);

        if ($arr[$mid] > $key) {
            $high = $mid - 1;
        } elseif ($arr[$mid] < $key) {
            $low = $mid + 1;
        } else {
            return $mid;
        }
    }

    return -1;
}

该代码实现了基本的二分法查找，通过输入数组和要查找的键来查找键的位置。

其中，$low为数组最小值的下标，$high为数组最大值的下标，$mid为中间值的下标。每一次循环，都将区间缩小一半，直到找到目标值或者缩小到区间为空。

示例1：

$arr = [1, 2, 3, 4, 5];
$key = 3;
$index = binary_search($arr, $key); // 2

if ($index !== -1) {
    echo "键为".$key."的元素下标为".$index;
} else {
    echo "键为".$key."的元素不存在";
}

数组 $arr 中包含了 1, 2, 3, 4, 5 五个数，要查找的键为3，则输出结果为“键为3的元素下标为2”。

示例2：

$arr = [1, 3, 5, 7, 9];
$key = 4;
$index = binary_search($arr, $key); // -1

if ($index !== -1) {
    echo "键为".$key."的元素下标为".$index;
} else {
    echo "键为".$key."的元素不存在";
}