class Solution {

private:

int binaryFind(vector &data, int begin, int end ,int k){

int ind = -1;

if(begin >= end) return -1;

int mid = (end + begin) / 2;

if(k == data[mid]) return mid;

if((ind = binaryFind(data,begin,mid,k)) != -1) return ind;

if((ind = binaryFind(data,mid+1,end,k)) != -1) return ind;

return -1;

}

public:

int GetNumberOfK(vector data ,int k) {

int ind = binaryFind(data,0,data.size(),k);

if(ind == -1) return 0;

int pos = ind;

int cnt = 1;

while(--pos >= 0 && k == data[pos]) ++cnt;

while(++ind < data.size() && k == data[ind]) ++cnt;

return cnt;

}

};