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

Limitations:

0 <= Array length <= 50000

Their thinking

  1. Use dichotomy to find one of the target elements
  2. Look around for the target element

code

class Solution {
    public int search(int[] nums, int target) {

        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int mid = (r - l) / 2 + l;
            if (nums[mid] == target) {
                int left = mid-1, right = mid+1;
                while (left >= 0 && nums[left] == target)
                    left--;
                while (right < nums.length && nums[right] == target)
                    right++;
                return right - left - 1;
            } else if (nums[mid] > target)
                r = mid - 1;
            else l = mid + 1;
        }
        return 0; }}Copy the code