题目描述

blablabla

改进的二分

java 代码

class Solution {
    public int getNumberOfK(int[] nums, int k) {
        if (nums == null || nums.length == 0) return 0;  //输入的数组不合法
        int n = nums.length - 1;  //数组末尾索引
        if (k > nums[n] || k < nums[0]) return 0;  //输入的k越界，不合法
        int first = getFirst(nums, 0, n, k);  //k第一次出现的位置
        if (first == -1) return 0;  //first=-1说明数组中没有k
        int last = getLast(nums, first, n, k);  //借用first的结果，降低计算量
        return last - first + 1;   //注意要+1
    }

    private int getFirst(int[] nums, int l, int r, int k) {
        if (l > r) return -1;  //递归结束条件
        int mid = (l + r) >> 1;  // >>1 比 /2效率高
        if (nums[mid] == k) {  //当中间值=k时
            if (mid == l || nums[mid - 1] != k)  //mid在最左边或它左边的数 != k
                return mid;  //说明mid就是第一个出现的k
            else r = mid - 1; 
        } else if (nums[mid] > k) r = mid - 1;
        else l = mid + 1;
        return getFirst(nums, l, r, k);
    }

    private int getLast(int[] nums, int l, int r, int k) {  //与上面同理
        if (l > r) return -1;
        int mid = (l + r) >> 1;
        if (nums[mid] == k) {
            if (mid == r || nums[mid + 1] != k)
                return mid;
            else l = mid + 1;
        } else if (nums[mid] > k) r = mid - 1;
        else l = mid + 1;
        return getLast(nums, l, r, k);
    }