剑指offer（37）数字在排序数组中出现的次数

/*public class Solution {
    public int GetNumberOfK(int [] array , int k) {
       if(array == null && array.length == 0){
           return 0;
       }
        int count = 0;
       for(int i = 0;i < array.length;i++){
           if(array[i] == k){
               count++;
           }
       }
        return count;
    }
}*/public class Solution {
    //看到排序数组的字样就要想到二分查找，用二分查找直接找到第一个k和最后一个k
    public int GetNumberOfK(int [] array , int k) {
       if(array == null || array.length == 0 || k < array[0] || k > array[array.length-1]){
           return 0;
       }
        int first = getFirstK(array, k, 0, array.length-1);
        int last = getLastK(array, k, 0, array.length-1);
        if(first != -1 && last != -1){
            return last - first + 1;
        }
        return 0;
    }
    
    public int getFirstK(int[] array, int k, int start, int end){
        while(start <= end){
            int mid = (start + end) >> 1;//mid是动态的，每次都是一个新的值，所以这一句要放在while循环里面
            if(array[mid] > k){
                end = mid - 1;
            }else if(array[mid] < k){
                start = mid + 1;
            }else if((mid - 1) >= 0 && array[mid - 1] == k){//这一句&&前后的两个语句是不能颠倒的。原因如下
                end = mid - 1;
            }else{
                return mid;
            }
        }
        return -1;
    }
    
    public int getLastK(int[] array, int k, int start, int end){
        while(start <= end){
            int mid = (start + end) >> 1;
            if(array[mid] > k){
                end = mid - 1;
            }else if(array[mid] < k){
                start = mid + 1;
            }else if((mid + 1) <array.length && array[mid + 1] == k){//这一句&&前后的两个子句是不能颠倒的，因为&&是短路的逻辑与，一旦前面的语句判断为0，则后面的语句是不执行的。按照顺序要先判断边界问题。
                start = mid + 1;
            }else{
                return mid;
            }
        }
        return -1;
    }
}