Sword finger offer notes: T53 - I. find numbers in the sorted array

T53 - I. Look up numbers in the sort array I

Count the number of times a number appears in the sort array .

Example 1:

Input : nums = [5,7,7,8,8,10], target = 8
Output : 2
Example  2:

Input : nums = [5,7,7,8,8,10], target = 6
Output : 0

Limit ：

0 <= The length of the array <= 50000

Ideas

Two points , seek target and target-1 The right border of , Subtraction is the answer

solution 1

class Solution {
    public int search(int[] nums, int target) {
        return rightMargin(nums, target) - rightMargin(nums, target-1);
    }

    int rightMargin(int[] nums, int target){
           int left =0, right =nums.length-1;
        while(left<=right){
            int mid = left+((right-left)>>1);
            if(nums[mid]>target){
                right = mid-1;
            }else if(nums[mid]<=target){
                left = mid+1;
            }
        }
        return left;
    }
}

Execution time ：0 ms, In all  Java  Defeated in submission **100.00%** Users of

Memory consumption ：41.3 MB, In all  Java  Defeated in submission **63.01%** Users of

Time complexity ：O(logn). The time complexity of binary search is O(logn)

Spatial complexity ：O(1). Just save the left and right boundaries and intermediate values