Search for a range Leetcode – Find first and last position of element in sorted array

Find first and last position of element in sorted array

In this article, we will look into an interesting problem asked in Coding Interviews related to Searching Algorithms. The problem is: Given a Sorted Array, we need to find the first and last position of an element in Sorted array. This problem is also known as Search for a range on Leetcode. We will look at different approaches to solve the problem along with their implementation and analyze the complexities of our approach.

Basically, we need to determine the first and last occurrence of a duplicate key element in the Array. Consider this array for example:

Sorted Array with Duplicate Elements.

Here, we can see an array of size 10 with duplicate elements 5 and 7. If we want to know the first and last occurrence of element 5, it will be at index 3 and 4 respectively. Similarly, for element 7, the first and last occurrence is at position/index 5 and 7 respectively.

Now let us look at our approaches to solve this problem.

Approach 1 (Using Linear Search)

In this method, we will follow these steps:

  • At first, we will traverse the array from the beginning or start index of the array. As soon as we get the target element, we store its index. This will indicate the first occurrence position of the target element. Then, we break out of the loop and stop traversing.
  • Now, to get the last index, we will start traversing from the end index of the array and as soon as we get the target element, we store its index. This will indicate the last occurrence of the element. Then, we simply print those indices.

Let us look at the code for this method:

Output:

Time Complexity: Here we perform a Linear Search to get the indexes if the the first occurrence is at second last element then we have to traverse the whole array. So, the overall runtime is O(n).

Approach 2 (Using Modified Binary Search-Optimal)

The idea or purpose of this approach is to minimize the runtime of the above method by using and modifying the Binary Search Algorithm. The breakdown of this approach is shown below:

  • Basically, We implement two functions:
    1. findStartingIndex(Array,target) -> To get the Starting Index or First Occurrence of Target element.
    2. findEndingIndex(Array,target) -> To get the Ending Index or Last Occurrence of Target element.
  • Now, for findStartingIndex() method, we will search the target by performing a modified binary search. We calculate mid = (low + high) / 2 (low =0 and high = Array_Size – 1). As the array is sorted, for each value of mid we need to perform operations based on three conditions.
    1. If(Arr[mid] >= target) -> This means if the element at index mid is greater than target element, then to get closer to target we need to update high = mid - 1 and search in the left half of the array. If the element is equal to target then also we need to update high, this will ensure we get as close as possible to the First Occurrence of the target.
    2. If the first condition does not hold true, it means the element is smaller than target, so we update low = mid + 1 and expand our search to the right half of the array.
    3. If(Arr[mid] == target) -> If we get the element at index mid equal to target, we store its index as a possible solution and continue our search until low<=high.
  • Similarly for findEndingIndex() method, we search the target by making some changes. The algorithm remains the same as the method discussed above only the conditions need to be changed.
    1. If(Arr[mid] <= target) -> If the element at index mid is smaller than target, then to get closer to target we update low = mid + 1, instead of high and continue searching in the right half of array. If the element is equal then also we update low and get close to the Last occurrence of the target.
    2. If the first condition is not true, we update high = mid -1 and search in the left half of array as element at mid is greater than the target.
    3. If(Arr[mid] == target) -> If the element is equal, we store its index and continue these steps until low<=high.

Let us look at the implementation of above approach:

Output:

Time complexity: We used Binary Search to get the first and last occurrence of the target element. We know binary search has runtime O(log n). Henceforth, the calls for findStartingIndex() and findEndingIndex() methods take O(log n) time each. So, the overall complexity is O(log n + log n) = O(log n). This is an optimal approach for this problem.

That’s all about Search for a range Leetcode – Find First and Last Position of Element in Sorted Array.

Was this post helpful?

Leave a Reply

Your email address will not be published. Required fields are marked *