Count Occurrences in a Sorted Array
Problem statement
You are given an integer array nums sorted in non-decreasing order and an integer x. Return how many times x appears in nums.
Write the binary search yourself: find the first position whose value is at least x (the lower bound) and the first position whose value is greater than x (the upper bound). Your solution should run in O(log n) time.
Function
countOccurrences(nums: int[], x: int) → intExamples
Example 1
nums = [1,2,2,2,3,5]x = 2return = 3The first value that is at least 2 is at index 1, and the first value greater than 2 is at index 4. So 2 appears 4 - 1 = 3 times.
Example 2
nums = [1,3,5,7]x = 4return = 0Both bounds land on index 2, the position of 5, because no value equals 4. The answer is 0.
Example 3
nums = [-4,-4,-4]x = -4return = 3Every element equals -4. The lower bound is 0 and the upper bound is 3, the array length, so the answer is 3.
Constraints
1 <= nums.length <= 10^5-10^9 <= nums[i], x <= 10^9numsis sorted in non-decreasing order.