PHP 基础二分查找代码实现

基础的二分查找就是:在一组有序的集合中,查找指定值,稍微延伸一下就是指定值在集合中多次出现,需要查询第一次出现的位置或者最后一次出现的位置。这种分三种情况讨论。二分查找的维基百科定义: 搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

无重复值的查找

function binarySearch($nums, $target) {
    $left = 0;
    $right = count($nums) - 1;
    while ($left <= $right) {
        $mid = (int)($left + ($right - $left) / 2);   // 防止 left + right 会整数溢出
        if ($nums[$mid] == $target) {
            return $mid;   // 匹配到就返回
        } elseif ($nums[$mid] > $target) {
            $right = $mid - 1;
        } elseif ($nums[$mid] < $target) {
            $left = $mid + 1;
        }
    }

    return -1;
}

return binarySearch([-1,0,3,5,9,12], 9);  // output: 4

查找指定值的左侧边界

function binarySearch($nums, $target) {
    $left = 0;
    $right = count($nums) - 1;
    while ($left <= $right) {
        $mid = (int)($left + ($right - $left) / 2);
        if ($nums[$mid] == $target) {
            $right = $mid - 1;   // 锁定左边,移动右边界
        } elseif ($nums[$mid] > $target) {
            $right = $mid - 1;
        } elseif ($nums[$mid] < $target) {
            $left = $mid + 1;
        }
    }

    if ($left >= count($nums) || $nums[$left] != $target)
        return -1;

    return $left;
}

return binarySearch([-1,0,3,5,9,9,9,12], 9);  // output: 4

寻找指定值的右侧边界

function binarySearch($nums, $target) {
    $left = 0;
    $right = count($nums) - 1;
    while ($left <= $right) {
        $mid = (int)($left + ($right - $left) / 2);
        if ($nums[$mid] == $target) {
            $left = $mid + 1;   // 锁定右边,移动左边界
        } elseif ($nums[$mid] > $target) {
            $right = $mid - 1;
        } elseif ($nums[$mid] < $target) {
            $left = $mid + 1;
        }
    }

    if ($right < 0 || $nums[$right] != $target)
        return -1;

    return $right;
}

return binarySearch([-1,0,3,5,9,9,9,12], 9);  // output: 6

参考链接:

  1. 二分查找解题框架思路 ,强烈推荐这个网站的作者
我来评几句
登录后评论

已发表评论数()

相关站点

+订阅
热门文章