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

第三十四题

方法一：暴力破解 直接统计 当出现数小于数组中的数时，返回结果

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        int times;
        for(int i =0;i<data.size();i++)
        {
            if(k==data[i])
                times++;
            if(k<data[i])
                break;
        }
        return times;
    }
};

方法二：二分查找，找到出现的数的左右边界

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        // 利用二分法 找左右边界
        // 边界的要求是 左边小于k,或者，右边大于k
        int ll=0,rr=0;
        int left=0,right=data.size();
        int middle;
        // 二分法找左边界，要求左边的值小于k，右边的值>=k
        while(left<right){
            middle = (left+right)/2;
            // 中间值太大，右边界缩小
            if(data[middle]>=k)
                right=middle;
            // 反之，左边界放大
            else
                left=middle+1;
        }
        ll = left;
        
        left=0;
        right=data.size();
        // 同理 二分法找右边界，就是要求绝对大于k的值
        while(left<right){
            middle=(left+right)/2;
            if(data[middle] > k)
                right=middle;
            else
                left=middle+1;
        }
        rr=left;
        return rr-ll;
    }
};