Introduction

Here I will find start and end index of a given element in a sorted array using Java programming language.

So it means in the sorted array I have to find the start and end indices of a particular element. The array may also contain duplicate elements.

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. Remember the index in an array starts at 0.

Find Start and End Indices

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

So, to find out the result in optimised 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 source code, I have defined two methods findStartIndex() and findEndIndex() to find start index and end index of a particular element in the array, respectively.

Source Code

download