题目描述：
给定一个长度为 n 的非降序数组和一个非负数整数 k ，要求统计 k 在数组中出现的次数
数据范围：0≤n≤1000,0≤k≤100，数组中每个元素的值满足 0≤val≤100
要求：空间复杂度 O(1)，时间复杂度 O(logn)
示例：
输入：
[1,2,3,3,3,3,4,5],3
返回值：
4
解题思路：
本题考察算法-搜索算法的使用。考虑到复杂度的要求，采用二分法的思路解题。具体实现列了三种写法：
解法一：二分查找
- 因题目中全是整数，此时可以将k加减一个小数，达到错位的目的。
- BinarySearch(data, k + 0.1)得到的是目标值最后一次出现位置的右侧，BinarySearch(data, k - 0.1)得到的是目标值首次出现的位置，相减刚好是出现的次数。
- BinarySearch函数执行二分查找，当左边界超过了右边界，说明此时的左边界是目标值的位置向上取整。
解法二：STL内置二分搜索算法-equal_range
- result是一个pair,里面存放了两个迭代器。
- first表示k首次出现的位置，second表示k最后一个出现位置的下一个位置。
解法三：模拟STL内置函数-lower_bound&upper_bound
- lower_bound寻找该值首次出现的位置。
- upper_bound寻找该值最后一次出现的位置，返回该位置的后一位。
测试代码：
解法一：二分查找
class Solution { public: // 二分查找 int BinarySearch(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加减一个小数，达到错位的目的 // BinarySearch(data, k + 0.1)得到的是目标值最后一次出现位置的右侧 // BinarySearch(data, k - 0.1)得到的是目标值首次出现的位置 // 相减刚好是出现的次数 return BinarySearch(data, k + 0.1) - BinarySearch(data, k - 0.1); } };
解法二：equal_range
class Solution { public: // 寻找目标值 int GetNumberOfK(vector<int> data ,int k) { // result是一个pair,里面存放了两个迭代器 // first表示k首次出现的位置，second表示k最后一个出现位置的下一个位置 auto result = equal_range(data.begin(), data.end(),k); return result.second - result.first; } };
解法三：lower_bound&upper_bound
class Solution { public: // 寻找目标值 int GetNumberOfK(vector<int> data ,int k) { // 寻找该值首次出现的位置 int first = LowerBound(data, k); // 寻找该值最后一次出现的位置，返回该位置的后一位 int second = UpperBound(data, k); return second - first; } // 寻找该值首次出现的位置 int LowerBound(vector<int>& data, int k) { int l = 0, r = data.size(); while(l<r) { int m = (l+r)/2; if(data[m]>=k) r = m; else l = m+1; } return l; } // 寻找该值最后一次出现的位置，返回该位置的后一位 int UpperBound(vector<int>& data, int k) { int l = 0, r = data.size(); while(l<r) { int m = (l+r)/2; if(data[m]>k) r = m; else l = m+1; } return l; } };
