Given an array of integer with duplicated elements. Find the first occurrence of a given number in the array.
For example: A = [1, 1, 1, 2, 2, 3, 3, 3, 4]. So, first occurrence of 2 is in index 3, first occurrence of 4 is in index 8.
The problem can be solved efficiently by using a modified binary search. In normal binary search we could have ended up in any of the duplicated element. So, in this case when we find a match then instead of stopping the search we could continue search for the element in the left. While doing so we can keep track of leftmost position where we found a match.
public static int searchFirstOccurance(final int[] a, final int key) { if (a[0] == key) { return 0; } int l = 0; int r = a.length - 1; int m = (l + r) / 2; int keyPosition = Integer.MAX_VALUE; while (l <= r) { m = (l + r) / 2; if (key == a[m]) { keyPosition = Math.min(keyPosition, m); r = m - 1; } else if (key < a[m]) { r = m - 1; } else if (key > a[m]) { l = m + 1; } } return keyPosition == Integer.MAX_VALUE ? -1 : keyPosition; }