To find last or rightmost position of an element in a sorted array. To find rightmost position in sorted array in Time Complexity O(logN).
See the following running code to find rightmost position in a sorted array:-
If Code output is -1 means element not found otherwise element is exists.
package com.dev.gcl3.search;
public class RightMostIndex {
public static void main(String[] args) {
int arr[] = {2,3,3,3,3};
int x = 3;
int rIndex = findRightMostIndex(arr, x);
System.out.println("Right Most Index: " + rIndex);
}
private static int findRightMostIndex(int[] arr, int x) {
return findRightMostIndex(arr, 0, arr.length-1, x);
}
//Time Complexity O(logN)
private static int findRightMostIndex(int[] arr, int l, int h, int x) {
if(l>h) {
return -1;
}
int mid = l+(h-l)/2;
if(arr[mid]==x) {
if(mid == h || arr[mid+1] != x) {//mid =0 means search data placed into 0 index
return mid;
}else {
return findRightMostIndex(arr, mid+1, h, x);
}
}else if(x > arr[mid]) {
return findRightMostIndex(arr, mid+1, h, x);
}else if(x < arr[mid]) {
return findRightMostIndex(arr, l, mid-1, x);
}
return -1;
}
}
Output:-
