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

方法一：简单不精致，面试官不满意
思路：排序数组就用二分法找到数字K,再遍历其左右统计次数即可。

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        if (data.empty())
            return 0;
        int low = 0, high = data.size() - 1,mid=0;
        while (low < high)
        {
            mid = low + (high - low) / 2;
            if (data[mid] > k)
                high = mid - 1;
            else if (data[mid] < k)
                low = mid + 1;
            else
            {
                break;

            }
        }
        int count = 0;
        if (data[mid] == k)
        {
            int i = mid, j = mid + 1;
            while (i>=0&&data[i]==k)
            {
                ++count;
                --i;
            }
            while (j<data.size()&& data[j] == k)
            {
                ++count;
                ++j;
            }
        }
        return count;
    }
};

方法2：递归

用二分查找直接找出第一个K和最后一个K

class Solution {
public:
    int GetFirstK(vector<int> data, int k,int start,int end)
    {
        if (start > end)
            return -1;
        int low = start, high = end, mid = low + (high - low) / 2;
        if (data[mid] == k)
        {
            if (mid != 0 && data[mid - 1] == k)
                high = mid - 1; 
            else
                return mid;
        }
        else if (data[mid] > k)
            high = mid - 1;
        else
            low = mid + 1;

        return GetFirstK(data, k, low, high);
    }

    int GetLastK(vector<int> data, int k, int start, int end)
    {
        if (start > end)
            return -1;
        int low = start, high = end, mid = low + (high - low) / 2;
        if (data[mid] == k)
        {
            if (mid != end && data[mid + 1] == k)
                low = mid + 1;
            else
                return mid;
        }
        else if (data[mid] > k)
            high = mid - 1;
        else
            low = mid + 1;
        return GetLastK(data, k, low, high);
    }

    int GetNumberOfK(vector<int> data, int k) {
        if (data.empty())
            return 0;

        int start = 0, end = data.size() - 1;
        int FirstK = GetFirstK(data, k, start, end);
        if (FirstK < 0)
            return 0;
        int LastK=GetLastK(data,k,start,end);
        //cout << FirstK << "  " << LastK << endl;
        return LastK - FirstK + 1;
    }
};