Binary Search — Rightmost Index of Duplicate

Requirements

• Receive an ascending array of integers, potentially containing repeated values, together with a target integer.
• Return the greatest index i for which arr[i] == target.
• Return -1 when no element equals the target.
• Your implementation must use binary search; a linear traversal is not allowed.

Implement the judged function using this exact signature:

def find_rightmost_index(arr, target):

Examples

Example 1

Input: arr = [0, 1, 1, 4, 4, 7], target = 4
Output: 4

The target appears at indices 3 and 4, so the final occurrence is at index 4.

Example 2

Input: arr = [2, 3, 6, 8, 10], target = 5
Output: -1

Because 5 is absent from the array, there is no valid matching index.

Example 3

Input: arr = [-3, -1, -1, -1, 2], target = -1
Output: 3

The three matching values occupy indices 1 through 3, making 3 the rightmost match.

Preparation

• Write both the leftmost-occurrence and rightmost-occurrence forms of binary search from memory, spending no more than about 10 minutes on each.
• Trace your rightmost-search implementation on [2, 5, 5, 5, 9] with target = 5; it should return index 3. Record lo, hi, and mid after every loop iteration.
• The interview allocation is approximately 30 minutes for resume discussion and 30 minutes for the coding task. Aim to finish the implementation within 15 minutes so that follow-ups such as counting matches or supporting non-integer values can be addressed.