php二分查找二种实现示例

PHP二分查找的实现

什么是二分查找算法？

二分查找，也称折半查找，是一种在有序数组中查找某一特定元素的搜索算法。它将目标值与数组中间位置的元素进行比较，如比中间位置的元素大，则目标值在数组的左半部分；如比中间位置的元素小，则目标值在数组的右半部分。不停地二分数组，直到找到目标值为止。通过这种方式，能够快速地找到特定元素，提高搜索效率。

二分查找算法在PHP中的实现

示例一

以下是在PHP中实现的基本二分查找算法：

/**
 * @param array $arr 有序数组
 * @param int $key 查找值
 * @return bool|int 返回查找值的下标，未找到则返回false
 */
function binary_search(array $arr, int $key)
{
    $low = 0; // 查找范围起点下标
    $high = count($arr) - 1; // 查找范围终点下标

    while ($low <= $high) {
        $mid = intval(($low + $high) / 2); // 中间下标

        if ($key === $arr[$mid]) {
            return $mid;
        }

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

    return false; //未找到
}

上述代码中的参数说明如下：

array $arr：要查找的有序数组

int $key：要查找的值

这段代码中，我们使用 while 循环来实现二分查找。首先确定要查找的范围，即查找起点和查找终点的下标。接着，计算出中间下标，与查找值进行比较。如果相等，则说明已经找到了目标值，返回它的下标。如果查找值小于中间值，则目标值在数组的左半部分，修改查找终点下标为中间下标减1，继续寻找。如果查找值大于中间值，则目标值在数组的右半部分，修改查找起点下标为中间下标加1，继续寻找。当查找起点下标大于查找终点下标时，表示已经遍历整个有序数组，未找到目标值，返回false。

示例二

以下是递归方式实现的PHP二分查找算法：

/**
 * @param array $arr 有序数组
 * @param int $low 查找起点下标
 * @param int $high 查找终点下标
 * @param int $key 查找值
 * @return bool|int 返回查找值的下标，未找到则返回false
 */
function binary_search_recursive(array $arr, int $low, int $high, int $key)
{
    if ($low <= $high) {
        $mid = intval(($low + $high) / 2); // 中间下标

        if ($key === $arr[$mid]) {
            return $mid;
        }

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

    return false; // 未找到
}

上述代码中的参数说明如下：

array $arr：要查找的有序数组

int $low：要查找范围的起点下标

int $high：要查找范围的终点下标

int $key：要查找的值

这段代码中，我们使用递归函数来实现二分查找。递归函数的实现方式与 while 循环方式类似，递归结束的条件为查找起点下标大于查找终点下标。递归函数中的变量同样需要在递归时进行传递。

总结

在PHP中，二分查找算法是提高搜索效率的重要算法之一。我们可以使用 while 循环或递归函数来实现二分查找算法。以上是两种不同实现方式的示例，使用者可以在实现时按照自身的需要进行修改和优化。