统计一个数字在升序数组中出现的次数

看了看难度中等，应该这样写不对吧（但是也过了）。

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

那就考虑数组超级长的情况吧！用二分查找！
如果数组超级长，而所找的数字出现次数，用上面那种方法是不太好的。再加上数组有序，用二分查找再好不过。
我们首先查找k，如果k存在，那会得到一个下标，然后从那个下标向前（注意数组前界），向后计数（注意数组后界）即可。如果没有找到k，后面计数的代码也不会执行。时间复杂度就一次查找加 m（k的个数）次循环。

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        int l = array.length;
        if(l==0){
            return 0;
        }
        int low = 0;
        int high = l-1;
        int mid = (low+high)/2;
        // 如果因为low>high不满足退出的就是没找到k
        while(array[mid]!=k&&low>high){
            if(array[mid]>k){
                high = mid-1;
            }else {
                low = mid+1;
            }
            mid = (low+high)/2;
        }
        // 没找到k，sum一次都不会增加。
        int sum = 0;
        int index = mid;
        while(index<l&&array[index]==k){
            sum++;
            index++;
        }
        index = mid-1;
        while(index>=0&&array[index]==k){
            sum++;
            index--;
        }
        return sum;
    }
}