《剑指offer》-数字在排序数组中出现的次数

统计一个数字在排序数组中出现的次数。

首先吐槽下出题人的用词，啥叫排序数组？“排序”是个动词好么，“有序”作为一个形容词表示状态，修饰“数组”，才是合适的。

题目考察二分查找，首先找到指定数字最先出现的位置，然后找到最后出现的位置，他们的距离+1就是个数。

class Solution14{
public:
    int GetNumberOfK(vector<int> data, int k){
        if (data.empty()){
            return 0;
        }
        int first = GetFirstIndex(data, k, 0, data.size() - 1);
        int last = GetLastIndex(data, k, 0, data.size() - 1);
        if (first > -1 && last > -1){
            return last - first + 1;
        }
        return 0;
    }
    int GetFirstIndex(vector<int>& data, int k, int start, int end){
        if (start > end) return -1;
        int mid = start + (end - start) / 2;
        if (data[mid] == k){
            if (mid == start || data[mid-1]!=k){
                return mid;
            }
            else{
                end = mid - 1;
            }
        }
        else{
            if (data[mid]>k){
                end = mid - 1;
            }
            else{
                start = mid + 1;
            }
        }
        return GetFirstIndex(data, k, start, end);
    }
    int GetLastIndex(vector<int>& data, int k, int start, int end){
        if (start > end) return -1;
        int mid = start + (end - start) / 2;
        if (data[mid] == k){
            if (mid == end || data[mid + 1] != k){
                return mid;
            }
            else{
                start = mid + 1;
            }
        }
        else{
            if (data[mid]>k){
                end = mid - 1;
            }
            else{
                start = mid + 1;
            }
        }
        return GetLastIndex(data, k, start, end);
    }
};