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

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param k int整型 
     * @return int整型
     */
    int GetNumberOfK(vector<int>& nums, int k) {
        if(nums.empty())  return 0;
        // write code here
        // 用二分查找找到左边界和右边界，然后相减
        int n = nums.size();
        int l=0, r=n-1;
        // 找左端点 
        while(l < r){
            int mid = l + r >> 1;
            if(nums[mid] >= k) r = mid;
            else l = mid + 1;
        }

        if(nums[r]!=k)  return 0;
        int L = r;

        l = 0, r = n-1;
        while(l < r){
            int mid = l + r + 1 >> 1;
            if(nums[mid] <= k) l = mid;
            else r = mid - 1;
        }

        return r - L + 1;

    }
};

解题思路

1. 使用二分查找定位target的首尾
2. 首尾相减+1得到target的数目

注意细节：判断target是否存在，二分查找的边界问题

时间复杂度：

O(logN), 其中N是nums的长度

进行了两次的二分查找