php如何实现统计一个数字在排序数组中出现的次数（代码）
程序员文章站
2024-03-30 20:42:09
统计一个数字在排序数组中出现的次数。 博客 www.51msk.cn 1.有序的数组查找，使用二分法2.二分法查找第一次出现的位置，二分法查找最后一次出现的位置，end - start +1 ......
统计一个数字在排序数组中出现的次数。
博客
left=getleft(data,k)
right=getright(data,k)
retun right-left+1
getleft data,k
left=0
right=arr.length-1
mid=left+(right-left)/2
while left<=right
if arr[mid]<k //关键
left=mid+1
else
right=mid-1
mid=left+(right-left)/2
return left
getright data,k
left=0
right=arr.length-1
mid=left+(right-left)/2
while left<=right
if arr[mid]<=k //关键
left=mid+1
else
right=mid-1
mid=left+(right-left)/2
return right
<?php
function getnumberofk($data, $k)
{
$left=getleft($data,$k);
$right=getright($data,$k);
return $right-$left+1;
}
function getleft($arr,$k){
$left=0;
$right=count($arr)-1;
$mid=intval($left+($right-$left)/2);
while($left<=$right){
if($arr[$mid]>=$k){//关键
$right=$mid-1;
}else{
$left=$mid+1;
}
$mid=intval($left+($right-$left)/2);
}
return $left;
}
function getright($arr,$k){
$left=0;
$right=count($arr)-1;
$mid=intval($left+($right-$left)/2);
while($left<=$right){
if($arr[$mid]<=$k){//关键
$left=$mid+1;
}else{
$right=$mid-1;
}
$mid=intval($left+($right-$left)/2);
}
return $right;
}
$arr=array(1,2,3,4,4,4,5);
$m=getnumberofk($arr,4);
var_dump($m);