题目描述：
统计一个数字在排序数组中出现的次数。
思路分析：
1. 直观思路是直接遍历一遍，统计。复杂度也只要O(n)。
2. 显然这道题要考察的内容不这么简单，实际上考虑二分的思想来完成。分别二分查找第一个k和最后一个k。具体来说，利用二分查找思想，找到k，再判断当前的前一个是否为k或是否为第一个元素，若是，则返回；否则即第一个k在前面，则右边界r左移，继续递归查找。对于最后一个k的查找思路类似。
代码：
思路二：
class Solution {
public:
int GetFirstK(vector<int>data, int k, int l, int r)
{
if(l>r)
return -;
int mid = (l+r)/;
if(data[mid]>k)
{
r = mid-;
}
else if(data[mid]<k)
{
l = mid+;
}
else
{
if((mid> && data[mid-]!=k) || mid==)
return mid;
else
r = mid-;
}
return GetFirstK(data, k, l, r);
}
int GetLastK(vector<int>data, int k, int l, int r)
{
if(l>r) //递归出口
return -;
int mid = (l+r)/;
if(data[mid]>k)
{
r = mid - ;
}
else if(data[mid]<k)
{
l = mid + ;
}
else
{
if((mid<data.size()-&&data[mid+]!=k) || mid == data.size()- )
return mid;
else
l = mid+;
}
return GetLastK(data, k, l, r);
}
int GetNumberOfK(vector<int> data ,int k) {
if(data.size()<=)
return ;
int first = GetFirstK(data, k, , data.size()-);
int last = GetLastK(data, k, , data.size()-);
if(first==- && last ==-)
return ;
else
return last-first+;
}
};