剑指offer——数字在排序数组中出现的次数

题目描述：
统计给定数字k在排序数组中出现的次数

思路1：最容易想到但是效率不高的一个方法就是遍历整个数组，统计k出现的次数(for循环就能解决，不赘述)
思路2：由于题目给出是排序数组，所以很容易想到二分查找，采用二分查找的思路，找到第一个k的下标和最后一个k的下标，即可统计出总共有多少个k

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        if(data.empty())
            return 0;
        int first=GetFirstK(data,k,0,data.size()-1);
        int last=GetLastK(data,k,0,data.size()-1);
        if(first>-1&&last>-1)
            return last-first+1;
        else//不合法，返回0
            return 0;
    }
    int GetFirstK(vector<int>& data,int k,int start,int end){
        if(start>end)//边界不合法
            return -1;
        int mid=(start+end)>>1;
        if(data[mid]==k){
            if((mid>0&&data[mid-1]!=k)||mid==0)//等于k的非数组首元素或者是数组首元素
                return mid;
            else
                end=mid-1;
        }else if(data[mid]<k)
            start=mid+1;
        else
            end=mid-1;
        return GetFirstK(data,k,start,end);
    }
    int GetLastK(vector<int>& data,int k,int start,int end){
        if(start>end)
            return -1;
        int mid=(start+end)>>1;
        if(data[mid]==k){
            if(mid<data.size()-1&&data[mid+1]!=k||mid==data.size()-1)
                return mid;
            else
                start=mid+1;
        }else if(data[mid]<k)
            start=mid+1;
        else
            end=mid-1;
        return GetLastK(data,k,start,end);
    }
};