419. Count Occurrences of Element in Sorted Array

Given a sorted array nums and an integer target, return the number of times target appears in the array. Solve in O(log n) time.

Input: A non-decreasing integer array nums and an integer target.

Output: An integer representing the count of target in nums.

Examples

Example 1

Input: [1,2,2,2,3,4,5], 2
Output: 3
Explanation: 2 appears at indices 1,2,3. last-first+1 = 3-1+1 = 3.

Example 2

Input: [1,1,1,1,1], 1
Output: 5
Explanation: All 5 elements are 1. Count = 5.

Example 3

Input: [1,2,3,4,5], 6
Output: 0
Explanation: 6 not in array. Count = 0.