//数字K在排序数组中出现的次数

//思路：用二分查找，找到第一个k和最后一个K

public class NumberCount {

    public int numberCount(int[] a,int k){

        if(a==null)

            return 0;

        int start=0;

        int end=a.length-1;

        int first=firstK(a,k,start,end);

        int last=endK(a,k,start,end);

        return last-first+1;

    }

    //通过二分查找，找到最后一个K

    private int endK(int[] a, int k, int start, int end) {

        if(a==null)

            return 0;

        int middle=(start+end)/2;

        if(a[middle]==k){

            if(a[middle]==k&&a[middle+1]!=k||middle==a.length-1)

                return middle;

            else

                 start=middle+1;

        }

        else if(a[middle]<k)

            start=middle+1;

        else

            end=middle-1;

        return endK(a,k,start,end);

    }

    //通过二分查找找到第一个K

    public int firstK(int[] a, int k, int start, int end) {

        if(a==null)

            return 0;

        int middle=(start+end)/2;

        if(a[middle]==k){

            if(middle==0||a[middle-1]!=k&&a[middle]==k)

                return middle;

            else

                end=middle-1;

        }

        else if(a[middle]<k)

            start=middle+1;

        else

            end=middle-1;

        return firstK(a,k,start,end);

    }

    public static void main(String[] args) {

        int[] a={1,3,3,3,7,4,5};

        NumberCount numberCount=new NumberCount();

        int number=numberCount.numberCount(a, 3);

        System.out.println(number);

    }

}