【剑指 offer】数字在排序数组中出现的次数。

1、题目描述

统计一个数字在排序数组中出现的次数。

例如输入排序数组[1, 2, 3, 3, 3, 3, 4, 5]和数字3，由于3在这个数组中出现了4次，因此输出4。

样例:

输入：[1, 2, 3, 3, 3, 3, 4, 5] , 3
输出：4

2、问题描述：

• 有序查找，一般首先考虑是否可以二分法。

3、问题关键：

• 如果要查找的数没有怎么办。
• 先二分法查找最左边的，再查找最右边的。
• 如果没有这个数，两种二分法查找的，一个小于k的最大值， 一个查找的是大于k的最小值，这两个位置差1。

4、C++代码：

class Solution {
public:
    int getNumberOfK(vector<int>& nums , int k) {
        if (!nums.size()) return 0;
        int n = nums.size();
        int first = getFirst(nums, 0, k, n - 1);
        int last = getLast(nums, 0, k, n - 1);
        return last - first + 1;
    }
    int getFirst(vector<int>& nums, int l, int k, int r) {
        while(l < r) {
            int mid = l + r >> 1;//小于等于k的最大值。
            if (nums[mid] >= k) r = mid;
            else l = mid + 1;
        }
        return l;
    }
    int getLast(vector<int>& nums, int l, int k, int r) {
        while(l < r) {
            int mid = l + r + 1 >> 1;//大于等于k的最小值。所以找不到k的时候，last比first大1，返回的结果也是正确的。
            if (nums[mid] <= k) l = mid;
            else r = mid - 1;
        }
        return l;
    }
};