To find the last occurrence of a given number in a sorted array, we use a variation of binary search that continues the search even after finding a match. This ensures we find the rightmost index where the element appears.
We begin by setting up two pointers—start
at the beginning of the array and end
at the end. We also keep a variable, say res
, initialized to -1
which will store the result.
Now, we repeatedly calculate the mid
index and compare the arr[mid]
value with the key
:
- Case 1: If
arr[mid]
is equal to the key
, it means we found a match. But we don't stop here—there might be more occurrences to the right. So we update res = mid
and shift our search to the right side by setting start = mid + 1
.
- Case 2: If
arr[mid] < key
, it means we need to move right, so we update start = mid + 1
.
- Case 3: If
arr[mid] > key
, the key (if present) must be on the left side, so we update end = mid - 1
.
We continue this loop until start
exceeds end
. At the end, if res
is still -1
, that means the key
was not found in the array.
Handling Different Scenarios
- If the key occurs once: The algorithm will detect and return the exact index on the first match.
- If the key occurs multiple times: It will skip earlier matches and eventually return the rightmost index.
- If the key does not exist: It will return
-1
after exhausting the search range.
- If the array is empty: The loop doesn't run, and
-1
is returned immediately.
This binary search variation is optimal with a time complexity of O(log n), making it ideal for large sorted arrays.