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

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        //如果二分查找过程中遇到的当前数不是k则按照正常的二分方法继续递归
        //如果当前遇到的数等于k则要在两边继续二分这样才能找到所有的k
        int high=data.size();
        return process(data, 0, high-1, k);
        
    }
    //该递归函数的意思是在low到high的范围上返回k出现的次数
    int process(vector<int> array,int low,int high,int k)
    {
        if(low>high)//base case
            return 0;
        int ans=0;
        int mid=(low+high)/2;//因为数据范围较小，所以不用担心low+high会越界
        if(array[mid]<k){//第一种情况：当前数小于k则按照正常的递归套路就行
            ans+=process(array,mid+1,high,k);
        }
        if(array[mid]>k){//第二种情况也是正常情况：也按照递归套路求解即可
            ans+=process(array, low, mid-1, k);
        }
        if(array[mid]==k)//第三种情况：此时应该向两边继续递归
        {
            ans++;//首先ans++，因为此时已经找到一个k了
            ans+=process(array, low, mid-1, k);
            ans+=process(array, mid+1, high,k);
        }
        return ans;
    }
};