0 votes
39 views
in Data Structure And Algorithm by (3.7k points)
Find last or rightmost positions of an element in a sorted array ?

1 Answer

0 votes
by (3.9k points)

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:- 
Right Most Index: 4

Share:- Whatsapp Facebook Facebook


Welcome to Developerhelpway Q&A, where you can ask questions and receive answers from other members of the community.

Categories

...