Given an array of sorted numbers, we have to find the right most occurrence of a number.
For example given an array {1,2,2,2,3}, the right most occurrence of 2 is at index 3 (0-based index).
This post is related to one of my previous posts ( Finding the left most occurrence in sorted array).
Similar to the above problem, we have to utilize binary search to solve this problem in O( log n ) time. Normal binary search returns any index which matches the given value. So, We have to customize binary search to find the right most instance.
In this modified approach, we have to check if we have already reached the end of the array or the middle is different from it’s next element. If it’s different, we return; otherwise we continue with right half of the array.
For example given an array {1,2,2,2,3}, the right most occurrence of 2 is at index 3 (0-based index).
This post is related to one of my previous posts ( Finding the left most occurrence in sorted array).
Similar to the above problem, we have to utilize binary search to solve this problem in O( log n ) time. Normal binary search returns any index which matches the given value. So, We have to customize binary search to find the right most instance.
In this modified approach, we have to check if we have already reached the end of the array or the middle is different from it’s next element. If it’s different, we return; otherwise we continue with right half of the array.
This function is similar C++ library implementation of upper_bound().
Here is the implementation in C++ which covers various test cases.