描述

给定一个长度为 n 的非降序数组和一个非负数整数 k ，要求统计 k 在数组中出现的次数

数据范围：0<=n<=1000,0<=k<=100，数组中每个元素的值满足0<=val<=100

要求：空间复杂度O(1)，时间复杂度O(logn)

思路1：遍历

直接遍历，时间复杂度O(n)

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        int count = 0;
        for(int num : array) {
            if(num == k) {
                count++;
            } else if(count > 0) {
                return count;
            }
        }
        return count;
    }
}

思路2：二分查找左右边界

例如：{5,7,7,8,8,10}，target=8，左边界（等于target）下标是3，右边界（大于target）下标是5，次数=右边界-左边界

需要注意的是临界值判断

二分法mid = i + (j - i) >> 1;这样写可以避免i+j导致的整型溢出

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        if(array.length == 0) {
            return 0;
        }
        int i = 0;
        int j = array.length - 1;
        //查找左边界，等于k
        while(i < j) {
            int mid = (i + j) >> 1;
            if(array[mid] < k) {
                //小于k舍弃
                i = mid + 1;
            } else {
                j = mid;
            }
        }
        int left = i;
        if(array[j] != k) {
            //目标值不存在
            return 0;
        }
        //右边界大于左边界，因此从左边界开始二分
        //注意这里不能减1，否则当数组长度为1时，right=left=0
        j = array.length;
        //查找右边界，大于k
        while(i < j) {
            int mid = (i + j) >> 1;
            //小于等于k舍弃
            if(array[mid] <= k) {
                i = mid + 1;
            } else {
                j = mid;
            }
        }
        int right = j;
        return right - left;
    }
}