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

一.题目描述
NC74数字在升序数组中出现的次数
题目链接:
https://www.nowcoder.com/practice/70610bf967994b22bb1c26f9ae901fa2?tpId=188&&tqId=38596&rp=1&ru=/activity/oj&qru=/ta/job-code-high-week/question-ranking
统计一个数字在升序数组中出现的次数。
二.算法(模拟)
要求数字在有序数组中出现的次数，那么直接遍历一遍数组是不是就是可以了？？下面是通过的代码:

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

时间复杂度：o(n)
空间复杂度：o(1) 没有利用额外的空间
优缺点：时间复杂度对于该题来说还是比较高，但是实现简单。
三.算法(二分)

暴力的方法无法将数组有序的条件利用上，因为数组是升序的，目标值如果有多个就是连在一起的，因此我们可以查找目标值的范围即：上界和下界。
下界：如果存在目标值，则指向第一个目标值，否则，如果不存在，则指向大于目标值的第一个值。
上界：不管目标值存在与否，都指向大于目标值的第一个值。
下面给出完整代码:

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        int n=data.size();
        int l=0;
        int r=n;
        int ans=0;
        // 找到升序序列中的下界
        while(l<r){
            int mid=(l+r)/2;
            if(data[mid]<k)
                l=mid+1;
            else
                r=mid;
        }
        int left=l;
        // 找到升序序列中的上界
        l=0;
        r=n;
        while(l<r){
            int mid=(l+r)/2;
            if(data[mid]<=k)
                l=mid+1;
            else
                r=mid;
        }
        int right=l;
        //上界减去下界为数字在升序数组出现的次数
        return right-left;
    }
};

时间复杂度：o(logn)
空间复杂度：o(1) 没有利用额外的空间
优缺点：时间复杂度低，但是实现起来没有算法二简洁