给定一个长度为 n 的非降序数组和一个非负数整数 k ，要求统计 k 在数组中出现的次数
数据范围：0 <= n <= 1000 , 0 <= k <= 1000 ≤ n ≤ 1000,0 ≤ *k ≤ 100，数组中每个元素的值满足 0 <= val <= 1000 ≤ val ≤ 100 要求：空间复杂度 O(1)O(1)，时间复杂度 O(logn)
示例1
输入：[1,2,3,3,3,3,4,5],3
返回值：4示例2
输入：[1,3,4,5],6
返回值：0方法：
谈到有序区间，加上 O(logn) 的时间复杂度，那么肯定是要使用二分查找，要注意的是我们要关心的当查找到对应的 k 值时候要处理的事情，而在查找 k 的时候还是和正常的二分是一样的，下面是步骤：
- 在主函数中调用去分别寻找 k 区间的左边界和右边界，这里以寻找左边界为例：
- 若 data[mid] < k ，说明要将区间范围缩小到 [mid + 1, right]
- 若 data[mid] > k ，说明要将区间范围缩小到 [left, mid - 1]
- 若 data[mid] = k，那么说明已经找到了 k，那么我们还是需要继续找最左边的k
- 判断一下 mid 是否已经为数组 data 的边界了，是的话说明 data[mid] 已经是第一个 k 了
- 如果不是数组 data 的边界，那么就判断一下 data[mid - 1] 是否为 k，是的话说明还有可能存在最左边的 k，那么继续二分查找，范围缩小到 [left, mid - 1]；若不是的话，则说明 data[mid] 已经是第一个 k 了
- 最后在主函数中让 右边界-左边界 就能得到区间内的个数了
class Solution {
private:
int GetFirstK(vector<int> data ,int k, int left, int right)
{
while(left <= right)
{
int mid = left + ((right - left)>>1);
if(data[mid] < k)
left = mid + 1;
else if(data[mid] > k)
right = mid - 1;
else
{
// 判断一下是否为最左边的数
if((mid > 0 && data[mid - 1] != k) || (mid == 0))
return mid;
right = mid - 1;
}
}
return -1;
}
int GetSecondK(vector<int> data ,int k, int left, int right)
{
while(left <= right)
{
int mid = left + ((right - left)>>1);
if(data[mid] < k)
left = mid + 1;
else if(data[mid] > k)
right = mid - 1;
else
{
// 判断一下是否为最右边的数
if((mid < data.size() - 1 && data[mid+1] != k) || (mid == data.size() - 1))
return mid;
left = mid + 1;
}
}
return -1;
}
public:
int GetNumberOfK(vector<int> data ,int k)
{
int first = GetFirstK(data, k, 0, data.size() - 1);
int second = GetSecondK(data, k, 0, data.size() - 1);
if(first == -1 || second == -1)
return 0;
return second - first + 1;
}
};