//得到已经排序的数组中指定数字k出现的次数
//已经排好序，所以想到用二分查找算法；
//重复次数=最后一次出现的位置-第一次出现的位置

#include <iostream>

using namespace std;
int GetFirstK(int *data,int length,int k, int start,int endd){
    if(start>endd)
        return -1;
    int mid=(start+endd)/2;//一分为二
    int midData=data[mid];
    if(midData==k){//中间恰好等于k，那么第一个k的位置要么就是这个中间；要么位于前半段数组
        if((data[mid-1]!=k && mid>0) || mid==0)
            return mid;
        else
            endd=mid-1;
    }
    else if(midData>k)
        endd=mid-1;
    else
        start=mid+1;
    return GetFirstK(data,length,k,start,endd);
}
int GetLastK(int *data,int length,int k,int start, int endd){
    if(data==NULL||start>endd)
        return -1;
    int mid=(start+endd)/2;//一分为二
    int midData=data[mid];
    if(midData==k){//中间恰好等于k，那么最后一个k的位置要么就是这个中间；要么位于后半段数组
        if((data[mid+1]!=k && mid+1<length) || mid+1==length){
            return mid;
        }
        else
            start=mid+1;
    }
    else if(midData<k){
        start =mid+1;
    }
    else
        endd=mid-1;
    return GetLastK(data,length,k,start,endd);

}
int GetKNumbers(int *data,int length,int k){
    if(!data || length<=0)
        return -1;
    int number=0;
    int first=GetFirstK(data,length,k,0,length-1);
    int endd=GetLastK(data,length,k,0,length-1);
    if(first>-1 && endd>-1)
        number= endd-first+1;
    return number;
}
int main()
{
    int data[]={1,2,3,3,3,3,4,5};
    cout<<GetKNumbers(data,8,1);
    return 0;
}