一：题目描述
统计一个数字在排序数组中出现的次数
如{1，2，3，3，3，3，4} 数字是3
因为数字3在数组中出现4次，所以返回4
二：解题思路
既然输入的数组是排序的，很自然想到二分查找，但是这里要注意一个细节，就是中间的数可能与要查找的数字相同，这种情况要细分
统计数字K出现的次数，如果我们能够找到K出现的第一个位置，和最后一个位置就可以统计K出现的次数
如何利用二分查找算法在数组中找到第一个K？
二分查找算法总是拿数组中间的数字和K做比较。如果中间的数大于K，那么K只有可能出现在数组的前半段，下一轮我们只在数组的前半段查找就可以。
如果中间的数小于K，那么K只可能在数组的后半段出现，下一轮我们只在数组的后半段查找即可。
如果中间的数等于K呢？
我们先比较这个数字是不是第一个K，如果中间的数前一个数不是K则，中间的数刚好是第一个K，如果中间的数的前一个数也是K，也就是说第一个K肯定在数组的前半段。
同理，我们可以找到K在数组中的最后一个位置。
三：代码实现
class Solution { public: //寻找数组中第一个K int FindFirstK(vector<int> data, int k, int start, int end){ int mid; while(start<=end){ mid=(start+end)/2; //如果中间的数与k相等，判断中间的数是否为第一个k if(data[mid]==k){ if((mid>0 && data[mid-1]!=k ) || mid==0) return mid; //中间的数是第一个k else end=mid-1; } else if(data[mid]>k) end=mid-1; else start=mid+1; } return -1;//如果没有找到k,返回-1； } //寻找数组中第最后一个K int FindLastK(vector<int> data, int k, int start, int end){ int mid; while(start<=end){ mid=(start+end)/2; //如果中间的数与k相等，判断中间的数是否为第一个k if(data[mid]==k){ if((mid<data.size()-1 && data[mid+1]!=k ) || mid==data.size()-1) return mid; //中间的数是第一个k else start=mid+1; } else if(data[mid]>k) end=mid-1; else start=mid+1; } return -1;//如果没有找到k,返回-1； } int GetNumberOfK(vector<int> data ,int k) { int num=0; if(data.size()<=0) return num; int first=FindFirstK(data,k,0,data.size()-1); int last=FindLastK(data,k,0,data.size()-1); if(first==-1 && last==-1) return num; else return last-first+1; } };