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

Given a sorted array of integers containing duplicates, write a program which returns the first index of an element.

Example:
Input:
array = {0, 1, 2, 2, 4, 5, 5, 5, 8};
num = 5;
Output:
Element 5 found at index 5


Question Asked in

Amazon, Microsoft


Video coming soon!



Subscribe for more updates


Preparing for interviews? IDeserve team is here to help.




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 smaller than desired element. This will give us first index of the desired element.


Hone your coding skills!




AngryNerds Practice platform »

Algorithm Visualization




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 first index of an element.
 *
 * @author Saurabh
 */
public class FirstIndexOfElementInSortedIntegerArrayWithDuplicates {

	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 == 0) || (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)


Contribution

  • Sincere thanks from IDeserve community to Saurabh Kumar for compiling current post.

    Saurabh Kumar

    Ninja Programmer