//二分查找关键字：while小等,mid=floor(left+right)/2,小left=mid+1,大right=mid-1,等返回mid
function binSearch($arr, $findUnit) {
sort($arr);
var_dump($arr);
$left = 0;
$right = count($arr)-1;
while($left<=$right) {
$mid = floor(($left+$right)/2);
if ($arr[$mid] < $findUnit) {
$left = $mid + 1;
} else if ($arr[$mid] > $findUnit) {
$right = $mid - 1;
} else if ($arr[$mid] == $findUnit) {
// 直接返回
return $mid;
}
}
return -1;
}
$arr = [2,2,33,35,35,36];
// var_dump(binSearch($arr, 36));
// die;
//左边界关键字：while小等,mid=floor(left+right)/2,小left=mid+1,大right=mid-1,等缩左right=mid-1,如果($left >= count($arr) || $arr[$left] != $findUnit)返-1，否则返回left
function binSearchLeft($arr, $findUnit) {
sort($arr);
var_dump($arr);
$left = 0;
$right = count($arr)-1;
while ($left <= $right) {
$mid = floor(($left+$right)/2);
if ($arr[$mid] < $findUnit) {
$left = $mid + 1;
} else if ($arr[$mid] > $findUnit) {
$right = $mid - 1;
} else if ($arr[$mid] == $findUnit) {
// 别返回，收缩左侧边界
$right = $mid - 1;
}
}
// 最后要检查 left 越界的情况
if ($left >= count($arr) || $arr[$left] != $findUnit)
return -1;
return $left;
}
var_dump(binSearchLeft($arr,2));
//die;
//右边界关键字：while小等,mid=floor(left+right)/2,小left=mid+1,大right=mid-1,等缩右left=mid+1,如果($right < 0 || $arr[$right] != $findUnit)返-1，否则返回right
function binSearchRight($arr, $findUnit) {
sort($arr);
$left = 0;
var_dump($arr);
$right = count($arr)-1;
while ($left <= $right) {
$mid = floor(($left+$right)/2);
if ($arr[$mid] < $findUnit) {
$left = $mid + 1;
} else if ($arr[$mid] > $findUnit) {
$right = $mid - 1;
} else if ($arr[$mid] == $findUnit) {
// 别返回，收缩右侧边界
$left = $mid + 1;
}
}
// 最后要检查 right 越界的情况
if ($right < 0 || $arr[$right] != $findUnit)
return -1;
return $right;
}
var_dump(binSearchRight($arr,37));