Here we will find start and end index of a given element in a sorted array using Java programming language. So it means the sorted array contains duplicate elements and we have to find the start and end indices of a particular element in the sorted array.

Let’s say a sorted array is given with the elements in it as [1 2 2 3 3 3 3 5 6] and you need to find out the start and end indices of element 3.

Therefore the start index is 3 and end index is 6.

Now you can iterate the array and find out the indices but it won’t give you the result in optimized way.

So to find out the result in optimized way you need to use Binary Search algorithm.

The complete source code using Java programming language is given below:

public class StartAndEndIndexOfValueInArray {
	public static void main(String[] args) {
		int[] arr = new int[] { 1, 1, 2, 2, 3, 3, 3, 3, 3, 5, 8, 6, 9 };
		StartAndEndIndexOfValueInArray findIdx = new StartAndEndIndexOfValueInArray();
		int totalElements = arr.length;
		int startIndex = findIdx.findStartIndex(arr, 0, totalElements, 3);
		int endIndex = findIdx.findEndIndex(arr, 0, totalElements, 3, totalElements);
		System.out.println("Start Index: " + startIndex + ", End Index: " + endIndex);
	}
	private int findStartIndex(int[] arr, int low, int high, int x) {
		if (high > low) {
			int mid = low + (high - low) / 2;
			if ((mid == 0 || x > arr[mid - 1]) && x == arr[mid]) {
				return mid;
			} else if (x > arr[mid]) {
				return findStartIndex(arr, mid + 1, high, x);
			} else {
				return findStartIndex(arr, low, mid - 1, x);
			}
		}
		return -1;
	}
	private int findEndIndex(int[] arr, int low, int high, int x, int totalElements) {
		if (high > low) {
			int mid = low + (high - low) / 2;
			if ((mid == totalElements - 1 || x < arr[mid + 1]) && x == arr[mid]) {
				return mid;
			} else if (x < arr[mid]) {
				return findEndIndex(arr, low, mid - 1, x, totalElements);
			} else {
				return findEndIndex(arr, mid + 1, high, x, totalElements);
			}
		}
		return -1;
	}
}

In the above code we have defined two methods findStartIndex() and findEndIndex() to find start index and end index of a particular element in the array, respectively.

Source Code

Thanks for reading.

Tags:

Leave a Reply

Your email address will not be published. Required fields are marked *