Search first occurrence of a duplicated element in a sorted array - Algorithms and Problem SolvingAlgorithms and Problem Solving

Search first occurrence of a duplicated element in a sorted array - Algorithms and Problem SolvingAlgorithms and Problem Solving

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;
}

Read full article from Search first occurrence of a duplicated element in a sorted array - Algorithms and Problem SolvingAlgorithms and Problem Solving