题解 | #数字在升序数组中出现的次数#

本题要求空间O(1),时间复杂度O(logn),很容易想到要使用二分查找来做，先找出比k大的下标r，再找出比k小的下标l，最后k有r-l-1个。

public:
    int GetNumberOfK(vector<int> data ,int k) {
        int n = data.size();
        //求比k大的下标
        //注意循坏退出条件，当l==r时，若data[mid]<=k，则mid+1为所求，否则为mid（好好理解此时l的取值）
        int l=0,r=n-1;
        while(l<=r)
        {
            int mid = (l+r)/2;
            if(data[mid] <= k) l=mid+1;
            else r=mid-1;
        }
        int ans = l;
        
        
        l = 0;r = n-1;
        while(l<=r)
        {
            int mid = (l+r)/2;
            if(data[mid] >= k) r=mid-1;
            else l=mid+1;
        }
        ans=ans-r-1;
        return ans;
    }
};