题目的主要信息：

• 给定一个长度为n的非降序数组和一个数字k，求k在数组中出现的次数
• 要求：空间复杂度$O(1)O(1)$，时间复杂度$O(lo{g}_{2}n)O(log\_2n)$

方法一：暴力遍历法（能过，时间不符合要求）

具体做法：

直接遍历数组data，查看每个数是否是等于k，然后计数即可。

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        int res = 0;
        for(int i = 0; i < data.size(); i++) //遍历数组
            if(data[i] == k) //记录出现的次数
                res++;
        return res;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，一次遍历
• 空间复杂度：$O(1)O(1)$，无额外空间

方法二：二分法

具体做法：

因为data是一个非降序数组，它是有序的，我们可以考虑二分查找。但是一个数组可能有多个k，于是我们要查找的并非常规二分法中k出现的位置，而是k出现的左界和k出现的右界。

再有因为数组中全是整数，因此我们可以考虑，用二分查找找到$k+0.5k+0.5$应该出现的位置和$k-0.5k-0.5$应该出现的位置，二者相减就是k出现的次数。

class Solution {
public:
    int bisearch(vector<int>& data, float k){ //二分查找
        int left = 0;
        int right = data.size() - 1;
        while(left <= right){ //二分左右界
            int mid = (left + right) / 2;
            if(data[mid] < k)
                left = mid + 1;
            else if(data[mid] > k)
                right = mid - 1;
        }
        return left;
    }
    int GetNumberOfK(vector<int> data ,int k) {
        //分别查找k+0.5和k-0.5应该出现的位置，中间的部分就全是k
        return bisearch(data, k + 0.5) - bisearch(data, k - 0.5);
    }
};

复杂度分析：

• 时间复杂度：$O(lo{g}_{2}n)O(log\_2n)$，两次二分查找，二分查找复杂度为$O(lo{g}_{2}n)O(log\_2n)$
• 空间复杂度：$O(1)O(1)$，无额外空间

方法三：库函数

具体做法：

我们还可以调用C++ STL的库函数equal_range来解决，该函数使用二分查找，找到数组中k值出现的左界和右界，最后右界减去左界就是我们要求的值。

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        auto res = equal_range(data.begin(), data.end(), k); //stl库函数
        return res.second - res.first; //左右界相减
    }
};

复杂度分析：

• 时间复杂度：$O(lo{g}_{2}n)O(log\_2n)$，equal_range函数依赖于二分查找
• 空间复杂度：$O(1)O(1)$，常数空间