Find last index of an element in a sorted array with duplicates

Algorithm/Insights

It is recommended to go through the binary search topic first.

We can use binary search to find the element with a slight modification.
While checking if the mid element is the desired element, ensure that mid+1 (if it exists) is greater than desired element. This will give us last index of the desired element.

Code Snippet

			
package com.ideserve.saurabh.questions;

/**
 * <b>IDeserve <br>
 * <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
 * Given a sorted array of integers containing duplicates, write a program which returns 
 * the last index of an element.
 *
 * @author Saurabh
 */
public class LastIndexOfElementInSortedIntegerArrayWithDuplicates {

	public static int searchElementAndReturnIndex(int[] array, int num) {
		if (array == null || array.length == 0) {
			return -1;
		}

		int start = 0;
		int end = array.length - 1;

		while (start <= end) {
			int mid = (start + end) / 2;
			if ( (array[mid] == num) && ((mid == end) || (array[mid + 1] > num)) ) {
				return mid;
			} else if (num < array[mid]) {
				end = mid - 1;
			} else {
				start = mid + 1;
			}
		}

		return -1;
	}

	public static void main(String[] args) {
		int[] array = {0, 1, 2, 2, 4, 5, 5, 5, 8};
		int num = 5;
		int index = searchElementAndReturnIndex(array, num);
		System.out.println("Element " + num + (index >= 0 ? (" found at index " + index) : " not found!"));
	}
}
		

Order of the Algorithm

Time Complexity is O(log n)
Space Complexity is O(1)