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.

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