面试官想要的答案一定不是O(n)，所以一定是O(logn)，以为是排序很容易想到是二分查找
从看到题到ac的思路[1, 2, 3, 3, 3, 3, 4, 5]
很容易想到在数组里面找到k的位置，然后用两个指针分别往左往右直到指向两端的3，那么答案就是right-left+1
后来想到如果3很长怎么办，那岂不是变成遍历了
所以想到了找2和4的大概位置，最后用两个while进行微调
没想到有一个用例是k不存在的，所以加了一个lindex>rindex判断

class Solution {
    public int getNumberOfK(int[] nums, int k) {
        if(nums==null || nums.length==0) return 0;
        int lindex=binarySearch(nums,0,nums.length-1,k-1);
        int rindex=binarySearch(nums,0,nums.length-1,k+1);
        lindex=lindex<0?0:lindex;
        rindex=rindex>=nums.length?nums.length-1:rindex;
        while(lindex>=0 && lindex<nums.length && nums[lindex]!=k) lindex++;
        while(rindex>=0 && rindex<nums.length && nums[rindex]!=k) rindex--;
        if(lindex>rindex) return 0;
        return rindex-lindex+1;
    }

    int binarySearch(int[] nums,int start,int end,int target){
        while(start<=end){
            int mid=start+(end-start)/2;
            if(nums[mid]==target) return mid;
            if(nums[mid]<target) start=mid+1;
            else end=mid-1;
        }
        return start;
    }
}