php二分查找法的基本使用- 醉丶春风的Blog

这篇文章主要介绍了php二分查找的二种实现示例，递归解法二分查找和非递归算法二分查找的示例,以及一些需要注意问题,的需要的朋友可以参考下

二分查找

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。其输入是一个有序的元素列表（必须是有序的），如果查找的元素包含在列表中，二分查找返回其位置，否则返回-1

思路

假设我们现在有下面一个数组, 查找元素17是否在其中

$arr = [8, 10, 13, 17, 23, 29, 38, 45, 67, 72, 75];

分解一下, 可以得到如下图的步骤:
其中low和high 代表待查找元素区间的边界下标, mid代表区间元素的中间下标

alt

从上图可以发现, 每次查找都会排除一半的元素, 查找速度非常快, 其时间复杂度为O(logn)

代码实现

这里我们用两种方式来实现二分查找, 分别是递归查找法和非递归查找法

非递归查找法

/**
 * 基础的二分查找
 * @param array $data 一个顺序结构的数组
 * @param int $number 要查找的数据
 * @return int 返回元素所在的下标或-1
 */
function binarySearch(array $data, int $number) {
    // 非正确的参数
    if (!is_array($data) || empty($data)) {
        return -1;
    }
    $low = 0;
    $high = count($data) - 1;

    while ($low <= $high) {
        $mid = intval(($high + $low) / 2);
        // mid元素大于给定的元素, 说明可以直接排除从mid开始到high中的所有元素, 将high等于mid-1
        if ($data[$mid] > $number) {
            $high = $mid - 1;
        // mid元素小于给定的元素, 说明可以直接排除从low开始到mid中的所有元素, 将low等于mid+1
        } elseif ($data[$mid] < $number) {
            $low = $mid + 1;
        } else { // 如果等于mid, 则返回mid
            return $mid;
        }
    }

    return -1;
}

递归查找法

/**
 * 递归二分查找
 * @param array $data 要查找的元素数组, 必须为有序数组
 * @param int $low 区间起点下标
 * @param int $high 区间终点下标
 * @param int $number 要查找的元素
 * @return int
 */
function binarySearchRecursion(array $data, int $low, int $high, int $number) {
    if (!is_array($data) || empty($data)) {
        return -1;
    }
    // 当low > $high时, 退出递归
    if ($low > $high) {
        return -1;
    }
    $mid = intval($low + $high);
    if ($data[$mid] > $number) {
        return binarySearchRecursion($data, $low, $mid-1, $number);
    } elseif ($data[$mid] < $number) {
        return binarySearchRecursion($data, $mid+1, $high, $number);
    } else {
        return $mid;
    }
}

需要注意的几点

这里有几个坑, 一不注意就会踩坑, 这里说明一下

1.循环退出条件

注意是 low<=high，而不是 low, 是因为每次更新low的时候, low都会在mid的基础上加1, 所以如果匹配到最后一次, 此时low是=high的, 这个时候是不能结束循环的

2.mid的取值

实际上，mid=(low+high)/2 这种写法是有问题的。因为如果 low 和 high 比较大的话，两者之和就有可能会溢出。改进的方法是将 mid 的计算方式写成 low+(high-low)/2。
更进一步，如果要将性能优化到极致的话，我们可以将这里的除以 2 操作转化成位运算 low+((high-low)>>1)。因为相比除法运算来说，计算机处理位运算要快得多。
注意不能写成low+(high-low)>>1, 因为位运算优先级比较低, 这样性质就变了
位运算: 左移1位*2, 右移一位/2

3.low和high的更新

low=mid+1，high=mid-1。注意这里的 +1 和 -1，如果直接写成 low=mid 或者 high=mid，就可能会发生死循环。比如，当 high=3，low=3 时，如果 a[3] 不等于 value，就会导致一直循环不退出。

优化后的代码

添加了是否在区间范围内的判断和mid的取值优化, 这里只有非递归实现

/**
 * 优化二分查找
 * @param array $data 一个顺序结构的数组
 * @param int $number 要查找的数据
 * @return int 返回元素所在的下标或-1
 */
function binarySearch(array $data, int $number) {
    // 非正确的参数
    if (!is_array($data) || empty($data)) {
        return -1;
    }

    $low = 0;
    $high = count($data) - 1;

    // 给定元素不在给定的区间范围内, 直接返回
    if ($number < $data[$low] || $number > $data[$high]) {
        return -1;
    }

    while ($low <= $high) {
        // 更新计算mid元素值
        $mid = $low+(($high-$low)>>1);
        // mid元素大于给定的元素, 说明可以直接排除从mid开始到high中的所有元素, 将high等于mid-1
        if ($data[$mid] > $number) {
            $high = $mid - 1;
            // mid元素小于给定的元素, 说明可以直接排除从low开始到mid中的所有元素, 将low等于mid+1
        } elseif ($data[$mid] < $number) {
            $low = $mid + 1;
        } else { // 如果等于mid, 则返回mid
            return $mid;
        }
    }

    return -1;
}

醉丶春风的Blog

千里之行, 始于足下