统计一个数字在排序数组中出现的次数。
博客 www.51msk.cn
1.有序的数组查找，使用二分法
2.二分法查找第一次出现的位置，二分法查找最后一次出现的位置，end – start +1
left=getLeft(data,k)right=getRight(data,k)retun right-left+1getLeft 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 leftgetRight 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<?phpfunction 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);
