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

以上是php如何實現統計一個數字在排序數組中出現的次數（代碼）的詳細內容。更多資訊請關注PHP中文網其他相關文章！