php实现折半查找

折半查找（二分查找）简介

折半查找是一种针对有序数组的高效查找算法，时间复杂度为 O(log n)。其核心思想是通过不断缩小查找范围，逐步逼近目标值。

PHP 实现折半查找

以下是一个完整的 PHP 实现示例，包含递归和非递归两种方式：

非递归实现

function binarySearch($arr, $target) {
    $left = 0;
    $right = count($arr) - 1;

    while ($left <= $right) {
        $mid = floor(($left + $right) / 2);

        if ($arr[$mid] == $target) {
            return $mid; // 找到目标，返回索引
        } elseif ($arr[$mid] < $target) {
            $left = $mid + 1; // 目标在右半部分
        } else {
            $right = $mid - 1; // 目标在左半部分
        }
    }

    return -1; // 未找到
}

// 示例调用
$sortedArray = [1, 3, 5, 7, 9];
$result = binarySearch($sortedArray, 5); // 返回 2

递归实现

function binarySearchRecursive($arr, $target, $left, $right) {
    if ($left > $right) {
        return -1;
    }

    $mid = floor(($left + $right) / 2);

    if ($arr[$mid] == $target) {
        return $mid;
    } elseif ($arr[$mid] < $target) {
        return binarySearchRecursive($arr, $target, $mid + 1, $right);
    } else {
        return binarySearchRecursive($arr, $target, $left, $mid - 1);
    }
}

// 示例调用
$sortedArray = [1, 3, 5, 7, 9];
$result = binarySearchRecursive($sortedArray, 7, 0, count($sortedArray) - 1); // 返回 3

关键注意事项

1. 数组必须有序：折半查找要求输入数组是升序或降序排列的，否则算法无法正常工作。
2. 边界条件：循环或递归终止条件是 $left <= $right，避免遗漏边界值。
3. 中间值计算：使用 floor 或 int 确保 $mid 为整数索引。

性能优化

• 对于超大数组，递归实现可能引发栈溢出，建议优先选择非递归方式。
• 若查找范围较大，可通过位运算优化中间值计算：

  $mid = ($left + $right) >> 1;