二分法

• 实现O(nlogn)
• 注意条件升序，二分条件

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param k int整型 
     * @return int整型
     */
    int count=0;
    void check(vector<int>& nums,int k,int left,int right)
    {
        if(left>right)
        {
            return ;
        }
        int mid=(left+right)/2;//中间偏左
        if(nums[mid]<k)
        {
            check(nums,k,mid+1,right);
        }
        else if(nums[mid]>k)
        {
            check(nums,k,left,mid-1);
        }
        else{

            int midr=mid;
            int midl=mid;
            while(midr<=right)
            {
                if(nums[midr]!=k)
                {
                    
                    break;
                }
                midr+=1;
            }
            while(midl>=left)
            {
                if(nums[midl]!=k)
                {
                    break;
                }
                midl-=1;
            }
            count+=midr-midl-1;
        }
    }
    int GetNumberOfK(vector<int>& nums, int k) {
        // write code here
        //logn 二分法
        check(nums,k,0,nums.size()-1);
        return count;
    }
};