php如何实现统计一个数字在排序数组中出现的次数（代码）

统计一个数字在排序数组中出现的次数。

博客

 

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