题目：

统计一个数字在排序数组中出现的次数。

思路：

1、顺序遍历

顺序扫描一遍数组，统计该数字出现的次数。

时间复杂度：O(n)

2、二分查找

假设我们需要找的数字是k，那么就需要找到数组中的第一个k和最后一个k出现的位置。

如何通过二分查找得到第一个k的位置呢？

取数组中间的数字与k作比较，

如果该数字比k大，那么k只能出现在前半部分，那么下一轮只能在前半部分找；

如果该数字比k小，那么k只能出现在后半部分，那么下一轮只能在后半部分找；

如果该数字等于k，需要判断这是不是第一个k，如果该数字的前一个数字不是k，那么该数字就是第一个k，否则需要在前半部分继续寻找第一个k；

寻找最后一个k的方法与寻找第一个k的方法一样。

代码：

#include 
     
      using namespace std;int getFirstK(int* data,int k,int start,int end){    while(start<=end){        int mid=start+((end-start)>>1);        if(data[mid]==k){            if((mid>0 && data[mid-1]!=k) || mid==0)                return mid;            else                end=mid-1;        }        else if(data[mid]>k)            end=mid-1;        else            start=mid+1;    }    return -1;}int getLastK(int* data,int length,int k,int start,int end){    while(start<=end){        int mid=start+((end-start)>>1);        if(data[mid]==k){            if((mid
     

在线测试OJ：

http://www.nowcoder.com/books/coding-interviews/70610bf967994b22bb1c26f9ae901fa2?rp=2

AC代码：

class Solution {public:    int GetNumberOfK(vector
     
       data,int k) {        int len=data.size();        if(len<=0)            return 0;        int first=getFirstK(data,k,0,len-1);        int last=getLastK(data,len,k,0,len-1);        if(first!=-1 && last!=-1)            return last-first+1;        return 0;    }    int getFirstK(const vector
      
        &data,int k,int start,int end){        int mid;        while(start<=end){            mid=start+((end-start)>>1);            if(data[mid]==k){                if((mid>0 && data[mid-1]!=k) || mid==0)                    return mid;                else                    end=mid-1;            }            else if(data[mid]>k)                end=mid-1;            else                start=mid+1;        }        return -1;    }    int getLastK(const vector
       
         &data,int length,int k,int start,int end){        int mid;        while(start<=end){            mid=start+((end-start)>>1);            if(data[mid]==k){                if((mid
        
         k)                end=mid-1;            else                start=mid+1;        }        return -1;    }};