数字在升序数组中出现的次数【Java版】

方法一：两次logN搜索 得左右边界

//使用两个二分查找O(logN)，找到目标数字的上下界
public class Solution {
    public int GetNumberOfK(int [] array , int k) {

        int left = 0;
        int right = array.length;//用于夹紧的左右范围  //右边为数组结束的后一个，不然右边界无法到达这里（见下方）
        while(left<right){//一直夹到left==right为止
            int mid = (left+right)/2;
            if(array[mid] < k){//左边界(找的是目标中最左边一个)
                left = mid+1;//注意是左边加一，不然最后容易夹不紧
            }
            else right = mid;
        }
        int leftBound = left;

        left = 0;
        right = array.length;//重置
        while(left<right){
            int mid = (left+right)/2;
            if(array[mid] <= k){//右边界(找的是第一个开始不是目标的位置) //与上面几乎对称，只是将<改为<=
                left = mid+1;
            }
            else right = mid;
        }
        int rightBound = left;
        return rightBound - leftBound;//可能为0    //如果寻找的值不存在，则由于没有等于这个情况，上下两个while输出的位置一致
    }
}
//时间复杂度：O(logN)
//空间复杂度O(1)

方法一升级版
由于升序数组为 int[] 类型，所以可以将上面程序中两个类似的代码提出来作为方法：

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        return find(array, k) - find(array, k-1);
    }
    public int find(int [] array , int k){//此方法找右边界
        int left = 0;
        int right = array.length;
        while(left<right){
            int mid = (left+right)/2;
            if(array[mid] <= k){
                left = mid+1;
            }
            else right = mid;
        }
        return left;//left==right
    }
}

方法二：一次logN搜索 得左边界

//先找到任意一个，然后再顺藤摸瓜
//绝大多数大数据的情况下，都是O(logN) //极端情况，要找的那个重复数量奇多无比O(N)
public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        int left = 0;
        int right = array.length;
        while(left < right){
            int mid = (left+right)/2;
            if(array[mid] < k)left = mid+1;
            else right = mid;
        }
        int count = 0;
        while(left <= array.length-1 && array[left++] == k)++count;//从左到右统计
        return count;
    }
}