[编程题]数字在排序数组中出现的次数

//参考剑指offer思路，先找到第一个索引找到第二个索引
public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        if(array==null||array.length==0){
            return 0;
        }
        int result=0;
        if(findLast(array,0,array.length-1,k)>-1&&findFirst(array,0,array.length-1,k)>-1){
           result=findLast(array,0,array.length-1,k)-findFirst(array,0,array.length-1,k)+1;
        }
        return result;
    }

    //找到第一个索引的函数
    public static int findFirst(int[] array,int start,int end,int k){
        //边界条件
        if(start>end){
            return -1;
        }
        int midIndex=(start+end)/2;
       //中间索引值刚好等于K时
        if(array[midIndex]==k){
            //判断是第一个吗
            //这里有个坑，先判断(midIndex-1)>=0再array[midIndex-1]!=k，不然会出现数组越界
            //下同
            if(((midIndex-1)>=0&&array[midIndex-1]!=k)||midIndex==0){
                return midIndex;
            }else{
                end=midIndex-1;
            }
           //中间索引值刚好大于K时
        }else if(array[midIndex]>k){
            end=midIndex-1;
        }else{
            start=midIndex+1;
        }

        return findFirst(array,start,end,k);
    }

    //找到最后一个索引的函数
    private static int findLast(int[] array,int start,int end,int k){
        //边界条件
        if(start>end){
            return -1;
        }
        int midIndex=(start+end)/2;
        if(array[midIndex]==k){
            //判断是最后一个吗
            if(((midIndex+1)<array.length&&array[midIndex+1]!=k)||midIndex==array.length-1){
                return midIndex;
            }else{
                start=midIndex+1;
            }
        }else if(array[midIndex]<k){
            start=midIndex+1;
        }else{
            end=midIndex-1;
        }

        return findLast(array,start,end,k);
}
}

时间复杂度与二分查找的相同：O(logn)
空间复杂度为O(1)