题目描述
统计一个数字在排序数组中出现的次数。
分析：
原来一直对二分法很模糊，对mid+1,还是mid,决定这两个差不多，今天自己打脸了，控制的不精准就是错误。
把边界确定更加准确点，[left,end]确定为闭区间，只要不在这个区间，就+1或者-1， 不要模糊，不要模糊两可
class Solution {
public:
int GetNumberOfK(vector<int> data ,int k) {
int right=data.size()-1;
if (getLastk(data,k,0,right)==-1) return 0;
return getLastk(data,k,0,right)-getFirstk(data,k,0,right)+1;
}
int getFirstk(vector<int>&data,int k,int left,int right){
while(left<=right){
int mid=(left+right)>>1;
if(data[mid]<k)
left=mid+1;
else if(data[mid]>k)
right=mid-1;
else if(mid-1>=0&&data[mid-1]==k)
right=mid-1;
else
return mid;
}
return -1;
}
int getLastk(vector<int>&data,int k,int left,int right){
while(left<=right){
int mid=(left+right)>>1;
if(data[mid]<k)
left=mid+1;
else if(data[mid]>k)
right=mid-1;
else if(mid+1<data.size()&&data[mid+1]==k)
left=mid+1;
else
return mid;
}
return -1;
}
};
