C++版 - 剑指offer面试题38：数字在已排序数组中出现的次数

#include<cstdio>
#include<vector>
using namespace std;
class Solution {
public:
    int GetNumberOfK(vector<int> data, int k) {
        int idx = biSearch(data,0, (int)data.size(), k);   // 某个k的位置为idx 
        if(idx == -1) return 0;  // 未找到 
        int sum = 1; // 如果能找到1个k，sum初始化为1 
        for(int j = idx - 1; j >= 0; j--){  // 统计之前的那个k所在位置idx的前面k出现的次数 
            if(data[j] == k) sum++;
            else break;
        }
        for(int j = idx + 1; j < (int)data.size(); j++){  // 统计之前的那个k所在位置idx的后面k出现的次数
            if(data[j] == k) sum++;
            else break;
        }
        return sum;
    }     
    int biSearch(vector<int> &data, int begin, int end, int k){
        if(begin >= end) return -1;
        int mid = (begin + end)/2;
        if(data[mid] == k) return mid;  // 如果在区间mid处找到，提前返回；否则递归地在前一半去找，否则在后一半去找，总能找到 
        int pos1, pos2 = -1;
        pos1 = biSearch(data,begin,mid,k); 
        if(pos1 != -1) return pos1;
        pos2 = biSearch(data,mid + 1, end,k); 
        if(pos2 != -1) return pos2;              
        return -1;
    }
};
// 以下为测试 
int main()
{
	Solution sol;
	vector<int> vec1={1,3,4,5};
	vector<int> vec2={6,5,3,3,1,0};	
	int res1 = sol.GetNumberOfK(vec1, 4);
	int res2 = sol.GetNumberOfK(vec2, 3);	
	printf("%d\n", res1);	
	printf("%d\n", res2);		
	return 0;
}