题解 | #数字在升序数组中出现的次数# 尽量使用更多的方法去挑战

/*
思路：
1，使用map，逐个计算
2，使用二分法，找到data[mid] = k，然后将mid向左右扩展，找到相同的值。
这样的简单题应该使用更多的方法来挑战一下。
*/
class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        int len = data.size();
        if (len == 0 || data[0] > k || data[len-1] < k) {
            return 0;
        }
        int left = 0, right = len - 1;
        while(left <= right) {
            int mid = (left + right) / 2;
            if (data[mid] > k) {
                right = mid - 1;
            } else if (data[mid] < k) {
                left = mid + 1;
            } else {
                int leftIndex = mid, rightIndex = mid;
                while(leftIndex >= left && data[leftIndex - 1] == data[leftIndex]) {
                    leftIndex--;
                }
                while(rightIndex <= right && data[rightIndex + 1] == data[rightIndex]) {
                    rightIndex ++;
                }
                return rightIndex - leftIndex + 1;
               
            }
        }
        return 0;
    }
};