421. Find the Last Occurrence of Target

Given a sorted array nums (may contain duplicates) and an integer target, return the index of the last (rightmost) occurrence of target. Return -1 if target is not present. Solve in O(log n).

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

Output: Index of the last occurrence of target, or -1.

Examples

Input: [1,2,2,3,3,3,4], 3
Output: 5
Explanation: 3 appears at indices 3,4,5. Last occurrence is index 5.

Input: [5,5,5,5,5], 5
Output: 4
Explanation: All elements are 5; last occurrence is index 4.

Input: [1,2,3,4,5], 9
Output: -1
Explanation: 9 absent.

Constraints

• 1 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9
• nums sorted non-decreasing

Asked by