统计一个数字在排序数组中出现的次数。
博客 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);