First and Last Occurrence of an Element

Problem statement

Given a sorted array with possibly duplicate elements, the task is to find indexes of the first and last occurrences of an element x in the given array.

For example, we have input arr[] = {1, 3, 5, 5, 5, 5, 67, 123, 125} and x = 5. The first occurrence is at index 2 and last occurrence is at index 5.

Let us look at another example. We have input arr[] = {1, 3, 5, 5, 5, 5, 7, 123, 125 } and x = 7. The first occurrence is at index 6 and the last occurrence is at index 6.

Solution: naïve approach

The naïve approach is to run a for loop and check given elements in an array.

• Run a for loop and for i = 0 to n-1.
• Take first = -1 and last = -1.
• When we find an element for the first time, we update first = i.
• We always update last = i whenever we find the element.
• We print first and last.

But the time complexity of this solution is O(n).

Solution: divide and conquer

An efficient solution to this problem is to use a Binary Search. The only condition will be that the array should be sorted, as Binary Search can only be applied on sorted arrays. Let us visualize how first and last can be calculated using Binary Search. The grey color in the input array denotes the mid value while performing a Binary Search.