题目描述：
统计一个数字在排序数组中出现的次数。
分析：
二分变形。二分查找最左边和最右边k的位置，然后相减加一就是结果。
代码：
class Solution {
public:
int GetNumberOfK(vector<int> data, int k) {
int dataSize = data.size();
if(dataSize == ) return ;
int firstK = GetPositionOfFirstK(data, k, , dataSize - );
if(firstK == -) return ; // k不存在
int lastK = GetPositionOfLastK(data, k, , dataSize - );
return lastK - firstK + ;
}
int GetPositionOfFirstK(vector<int> data, int k, int left, int right) { // 二分找最左的k的位置
int mid = (left + right) >> ;
while(left < right) {
if(data[mid] > k) {
right = mid - ;
} else if(data[mid] < k) {
left = mid + ;
} else {
if(data[left] != k) left++;
else return left;
right = mid;
}
mid = (left + right) >> ;
}
return data[mid] == k ? mid : -;
}
int GetPositionOfLastK(vector<int> data, int k, int left, int right) { // 二分找最右的k的位置
int mid = (left + right) >> ;
while(left < right) {
if(data[mid] < k) {
left = mid + ;
} else if(data[mid] > k) {
right = mid - ;
} else {
if(data[right] != k) right--;
else return right;
left = mid;
}
mid = (left + right) >> ;
}
return data[mid] == k ? mid : -;
}
};