[PHP] 演算法-統計一個數字在排序數組中出現的次數的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]<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);