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