PHP基础二分查找代码实现

36次阅读

共计 1375 个字符，预计需要花费 4 分钟才能阅读完成。

原文链接: 何晓东技术博客

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

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

参考链接：