2020-05-31-PHP 基础二分查找代码实现

layout: posttitle: PHP 基础二分查找代码实现
subtitle: PHP 基础二分查找代码实现
date: 2020-05-31
author: he xiaodong
header-img: img/default-post-bg.jpg
catalog: true
tags:
- Go
- PHP
- LeetCode
- 二分查找

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

无重复值的查找

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. 二分查找解题框架思路，强烈推荐这个网站的作者

最后恰饭 阿里云全系列产品/短信包特惠购买 中小企业上云最佳选择 阿里云内部优惠券