算法1

(递归) $O(logn)$

1. 二分法找到k的位置，如果二分找到的位置，比K大，就在前部分找，比K小就在后部分找
2. 如果找的了k，他的前一个不是K，则这个位置是第一个k，如果前一个还是k，就用二分法在前半部分找第一个k，最后返回第一个K的位置即可
3. 如果找的了k，他的后一个不是K，则这个位置是最后一个k，如果后一个还是k，就用二分法在后半部分找最一个k，最后返回最后一个K的位置即可
4. 然后相减加一即可

Java 代码

class Solution {
    public int getNumberOfK(int[] array, int k) {
        int num = 0;

        if(array!=null&&array.length>0){
            int first = GetFirstK(array,k,0,array.length-1);
            int last = GetLastK(array,array.length,k,0,array.length-1);

            if(first>-1&&last>-1)
                num = last-first+1;
        }

        return num;
    }

    public int GetFirstK(int[] array,int k,int start,int end){
        if(start>end){
            return -1;
        }
        int midIndex = (start+end)>>1;
        int midData = array[midIndex];

        if(midData == k){
            if((midIndex>0&&array[midIndex-1]!=k)||midIndex==0){
                return midIndex;
            }else{
                end = midIndex-1;
            }
        }
        else if(midData>k){
            end = midIndex-1;
        }else{
            start = midIndex+1;
        }
        return GetFirstK(array,k,start,end);

    }

    public int GetLastK(int[] array,int len ,int k,int start,int end){
        if(start > end)
            return -1;

        int midIndex = (start+end)>>1;
        int midData = array[midIndex];

        if(midData == k){
            if((midIndex<len-1&&array[midIndex+1]!=k)||midIndex==len-1){
                return midIndex;
            }else{
                start = midIndex+1;
            }
        }
        else if(midData>k){
            end = midIndex-1;
        }else{
            start = midIndex+1;
        }
        return GetLastK(array,array.length,k,start,end);
    }

}