First and Last Occurrence of an Element
Explore how to find the first and last positions of a given element in a sorted array using a divide and conquer strategy. This lesson helps you understand and implement a binary search-based approach that runs faster than the naïve method, especially on large datasets, enhancing your problem-solving skills with sorted arrays.
We'll cover the following...
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.