JZ37：数字在升序数组中出现的次数

方法1：遍历，时间复杂度为O(n);

    public static int GetNumberOfK1(int [] array , int k){
        if(array.length==0){
            return 0;
        }
        int count=0;
        for(int i=0;i<array.length;i++){
            if(array[i]==k){
                count++;
            }
        }
        return count;
    }

方法2：利用二分查找，可以查找k-0.5和k+0.5的下标，做差。就是k在数组中出现的次数

    public static int GetNumberOfK2(int[] array,int k){
        return binSearch(array,k+0.5)-binSearch(array,k-0.5);
    }
    public static int binSearch(int[] array,double k){
        int start=0;
        int end=array.length-1;
        while(start<=end){
            int mid=start+((end-start)>>1);
            if(k<array[mid]){
                end=mid-1;
            }
            else{
                start=mid+1;
            }
        }
        return start;
    }

方法3：二分查找，用递归二分法找到第一个k和最后一个k，然后得到个数

    public static int GetNumberOfK3(int[] array,int k){
        int num=0;
        if(array.length==0){
            return 0;
        }
        int firstK=getFirstK(array,k,0,array.length-1);
        int lastK=getLastK(array,k,0,array.length-1);
        if(firstK>=0 && lastK>=0){
            num=lastK-firstK+1;
        }
        return num;
    }
    //找到第一个出现的数字的下标
    public static int getFirstK(int[] array,int k,int start,int end){
        while (start <= end) {
            int mid = start + ((end - start) >> 1);
            if (k <= array[mid])
                end = mid - 1;
            else
                start = mid + 1;
            }
        if (start < array.length && array[start] == k)
            return start;
        else
            return -1;
    }
    //找到最后一个出现的数字的下标
    public static int getLastK(int[] array,int k,int start,int end){
        while(start<=end){
            int mid=start+((end-start)>>1);
            if(k>=array[mid]){
                start=mid+1;
            }
            else{
                end=mid-1;
            }
        }
        if(end>=0 && array[end]==k){
            return end;
        }
        else
            return -1;
    }