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

解法：二分

数组已经排好序，那么直接分别查找上下界即可
时间复杂度O(logn)，空间复杂度O(1)

  1. class Solution {
  2. public:
  3.     int getNumberOfK(vector<int>& nums , int k) {
  4.         if (nums.empty()) return 0;
  5.         if (k < nums[0] || k > nums[nums.size() - 1]) return 0;
  7.         int l = 0, r = nums.size() - 1;
  8.         while (l < r) {
  9.             int mid = l + r + 1 >> 1;
  10.             if (nums[mid] <= k) l = mid;
  11.             else r = mid - 1;
  12.         }
  14.         int right = l;
  16.         l = 0, r = nums.size() - 1;
  17.         while (l < r) {
  18.             int mid = l + r >> 1;
  19.             if (nums[mid] >= k) r = mid;
  20.             else l = mid + 1;
  21.         }
  23.         int left = l;
  25.         return right - left + 1;
  26.     }
  27. };