php获取一个数字在排序数组中出现的次数

统计一个数字在排序数组中出现的次数。

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]

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

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,5);

$m=GetNumberOfK($arr,4);

var_dump($m);

（编辑：安卓应用网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!