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

解法1：暴力求解：循环统计

查找数组中某个目标，不管数组是否有序，直接遍历一遍即可

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
       if(array.length==0 || array==null){
           return 0;
       }
        int count=0;
        for(int i=0;i<array.length;i++){
            if(array[i]==k){
                count++;
            }
        }
        return count;
    }
}

解法2：二分：第一次出现和最后一次出现的下标

因为有序，所以目标值target如果有多个，肯定是连在一起。又已知我们可以在有序数组中查找任意一个值，因此我们可以先查找目标范围的下界和上界。

public class Solution {
    public int GetNumberOfK(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 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 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;
    }
}