题解 | 数字在升序数组中出现的次数

#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型vector
     * @param k int整型
     * @return int整型
     */

    int GetLen(vector<int>& nums, int left, int right, float k) {
        int mid;
        while (left <= right) {
            mid = (left + right) / 2;
            if (k < nums[mid])  right = mid - 1;
            if (k > nums[mid])  left = mid + 1;
        }
        return left;
    }
    int GetNumberOfK(vector<int>& nums, int k) {
        // write code here
        if (nums.empty()) return 0;
        int left = 0, right = nums.size() - 1;
        return GetLen(nums, left, right, k+0.5)-GetLen(nums, left, right, k-0.5);
    }
};

二分的精髓在于左边只有小的时候才移动，右边只有大的时候才移动，所以每次检验一定是左边比要找到的小于等于，右边一定是大于等于要找的。

那么最后两个一定是要找的东西的两边值（即使一边有出界可能），根据整除特性，会找到left那个作为最后的mid，这个值是小于要求的值的，所以left会到比这个东西大的地方去。

因此我们找到的左值一定是比这个东西大的最小值，也就是说我的代码会找到k值第一个和k+1值第一个，两个坐标相减就会是k的持续长度（k出现的次数）。

时间复杂度为O(logn)，空间复杂度是O(1)。