数字在排序数组中出现的次数（二分查找）

统计一个数字在排序数组中出现的次数。例如：排序数组{1,2,3,3,3,3,4,5}，和数字3，由于3在这个数字中出现了4次，因此输出4。

解法1：顺序扫描，统计该数字出现的次数，时间复杂度为O(n)。

解法2：利用二分查找，找到一个数字，由于该数字可能出现多次，有可能该数字前后都有可能是所找的数字，因此向两边顺序扫描，找出第一个该数字和最后一个该数字。由于数字在长度为n的数组中有可能出现O(n)次,所以时间复杂度为O(n)。

这两种解法在本质上是一样的。

解法3：更好的利用二分查找，找到第一个该数字的位置，找到最后一个该数字的位置。

二分查找总是用中间的数字与所找的数字K进行比较，如果中间的数字比K小，向后找；如果中间的数字比K大，向前找；如果相等，我们来进行处理。

假设我们要找第一个K，如果中间数字是K，前一个数字不是K，则中间数字就是我们要找的第一次出现的K；如果中间数字是K,前一个数字也是K,说明第一次出现的K在前面，我们继续向前找。

同样的方法我们可以找到最后一个K。判断中间数字是不是最后一个K，可以看中间数字的后一位是不是K,不是K，则中间数字就是最后一个K；后一个数字是K，则继续向后找。

class Solution { public: int GetFirstK(vector<int>data,int length,int k,int start,int end) { if(start > end) return -1; int middleindex = (start + end)/2 ; int middledata = data[middleindex]; if(middledata == k) { if((middleindex > 0 && data[middleindex -1] != k) || middleindex == 0) return middleindex; else end = middleindex-1; } else if(middledata > k) end = middleindex-1; else start = middleindex +1; return GetFirstK(data,length,k,start,end); } int GetLastK(vector<int>data,int length,int k,int start,int end) { if(start > end) return -1; int middleindex = (start + end)/2 ; int middledata = data[middleindex]; if(middledata == k) { if((middleindex < length-1 && data[middleindex +1] != k) || middleindex == length-1) return middleindex; else start = middleindex+1; } else if(middledata > k) end = middleindex-1; else start = middleindex +1; return GetLastK(data,length,k,start,end); } int GetNumberOfK(vector<int> data ,int k) { int number = 0; int length = data.size(); if(length >0) { int first = GetFirstK(data,length,k,0,length-1); int last = GetLastK(data,length,k,0,length-1); if(first >-1 && last >-1) number = last - first +1; } return number; } };

GetFirstK,GetLastK,都是利用二分查找在数组中查找一个数字，时间复杂度是O(logn)，因此总的时间复杂度也是O(logn)。