Topic describes

Count the number of occurrences of a number in a sorted 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

How to solve the problem: binary method

Because we’re looking in a sorted array, we can use dichotomy.

  1. Find the last bit in the array equal to target by dichotomy
  2. Again, use dichotomy to find the first digit in the array less than target
  3. Subtracting the idx found in step 1,2 is the number of targets

Sample code:

def search(self, nums: List[int], target: int) - >int:
    l, r = 0.len(nums) - 1
    while l <= r:
        mid = (l + r) // 2
        if nums[mid] <= target:
            l = mid + 1
        else:
            r = mid - 1
    right = l
    if r >= 0 andnums[r] ! = target:If the target is not found on the first attempt, the target can be returned early
        return 0
    l = 0
    while l <= r:
        mid = (l + r) // 2
        if nums[mid] < target:
            l = mid + 1
        else:
            r = mid - 1
    left = r

    return right - left - 1
Copy the code