基础的二分查找就是：在一组有序的集合中，查找指定值，稍微延伸一下就是指定值在集合中多次出现，需要查询第一次出现的位置或者最后一次出现的位置。这种分三种情况讨论。二分查找的维基百科定义：搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。
无重复值的查找
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
参考链接：
- 二分查找解题框架思路，强烈推荐这个网站的作者
