php 折半查找 二叉树查找,有序表查找---折半查找算法

折半查找，也称为二分查找，是一种常见的查找算法。它是针对有序数组进行查找的。具体步骤如下：

1. 确定查找范围的左右边界，分别为 low 和 high，初始值分别为数组的第一个和最后一个元素的下标。
2. 计算中间位置 mid，即 mid = (low + high) / 2。
3. 比较中间位置的元素与要查找的值。如果相等，返回 mid；如果小于要查找的值，说明要查找的元素在右半部分，将 low 赋值为 mid + 1；如果大于要查找的值，说明要查找的元素在左半部分，将 high 赋值为 mid - 1。
4. 循环执行第 2 步到第 3 步，直到 low 大于 high，表示查找失败。

下面是 PHP 代码实现：

function binarySearch($arr, $target) {
    $low = 0;
    $high = count($arr) - 1;

    while ($low <= $high) {
        $mid = intval(($low + $high) / 2);
        if ($arr[$mid] == $target) {
            return $mid;
        } elseif ($arr[$mid] < $target) {
            $low = $mid + 1;
        } else {
            $high = $mid - 1;
        }
    }

    return -1;
}

除了折半查找，还有二叉树查找和有序表查找。二叉树查找是利用二叉树结构进行查找，每次比较当前节点的值与目标值的大小关系，然后根据大小关系往左或者往右走，直到找到目标值或者走到叶子节点为止。有序表查找是将有序表分成若干个子表，然后根据目标值与子表的范围比较，确定目标值可能在哪个子表中，然后再在该子表中进行折半查找。这两种算法的实现比较复杂，这里就不再赘述了。