Search from the end in a sorted array (variant)

Problem

You receive an integer array nums of length n, ordered from smallest to largest with equal values allowed, along with an integer target.

Search with the array's right side in mind, and report the greatest index containing target. Return -1 when target is absent.

Note: Treating the search as beginning at the right means selecting the final matching occurrence. Either a scan or binary search is acceptable, but you should be able to discuss its time cost.

Follow-up

When repeated values are common, how can you guarantee that the returned index is the final match? Is an O(log n) approach possible?

I/O

• Input: an integer array nums and an integer target
• Output: an integer representing target's last index, or -1 when no match exists

Constraints

• 0 <= n <= 2 * 10^5
• -10^9 <= nums[i], target <= 10^9
• nums is arranged in non-decreasing order

Examples

1. nums = [0,4,4,4,9], target = 4 -> 3 Index 3 is the rightmost location whose value is 4.
2. nums = [7,7,7], target = 7 -> 2 Every element matches, so the final index is 2.
3. nums = [-3,0,6,8], target = 5 -> -1 The requested value does not occur in the array.
4. nums = [], target = 0 -> -1 An empty array contains no matching index.
5. nums = [5,5,5,5], target = 5 -> 3 The last copy of 5 appears at index 3.

Example

Input:
[0,4,4,4,9]
4

Output: 3

nums = [0, 4, 4, 4, 9]
target = 4

3

The rightmost occurrence of 4 is at index 3.