Problem

Given a sorted array and an element, find the first occurrence of key in array.  As array can contain duplicate values, there can be multiple occurrences of same element, problem is to find first index.

Examples

Example 1:

1
2

Input: a = [1, 4, 4, 10, 10, 15, 20], target = 10
Output: 3

Solution

A brute force solution involves scanning the entire array and comparing each A[index] with the key. If A[index] == key, return the index. This method has a worst-case time complexity of ( O(N) ). Can we improve this?

The brute force approach doesn’t leverage the fact that the array is sorted. Instead, we can use Binary Search on Sorted Array. When there are no duplicates, finding the first instance with binary search is straightforward. How can we adapt this for arrays with duplicates?

Method 1 - Binary Search Variant

If target == a[mid], update firstPosition to mid. However, to find the very first occurrence of the target, continue checking the left part of the array for a lower position where the target might appear.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

public int binarySearchFirstPosition(int[] a, int target) {
	int start = 0;
	int end = a.length-1;

	int firstPosition = -1;
	
	while(start <= end) {
		int mid = (start + end)/2;

		if(target == a[mid]) {
			// Found target, update firstPosition and move to the left to find a smaller position by setting end=mid-1
			firstPosition = mid;
			end = mid-1;
		} else if (target < a[mid]) {
			end = mid-1;
		} else {
			start = mid+1;
		}
	}

	return firstPosition;
}