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:
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.
|
1 2 3 4 5 6 7 |
Input: Array = {2,3,4,5,5,7,7,7,9,11}, target = 7 Output: 5,7 // Comma separated Index of First and Last Occurrence. Input: Array = {5,6,6,6,7,8,8,10}, target = 8 Output: 5,6 |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
import java.util.*; public class Example { static void findFirstAndLastPosition(int arr[],int n,int target) { // We initialize first and last as -1 if the target is not present in the array. int first = -1; int last = -1; for(int i=0;i<n;i++) { if(arr[i] == target) { first = i; break; } } for(int i=n-1;i>=0;i--) { if(arr[i] == target) { last = i; break; } } System.out.println("The First occurrence of "+target+" at index : "+first+" and the Last occurrence is at index : "+last); } public static void main(String args[]) { int arr[] = new int[]{2,3,4,5,5,7,7,7,9,11}; int n = arr.length; int target = 7; findFirstAndLastPosition(arr,n,target); } } |
Output:
|
1 2 3 |
The First occurrence of 7 at index : 5 and the Last occurrence is at index : 7 |
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).
Further reading:
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:
findStartingIndex(Array,target)-> To get the Starting Index or First Occurrence of Target element.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 calculatemid = (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.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 updatehigh = mid - 1and 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.- If the first condition does not hold true, it means the element is smaller than target, so we update
low = mid + 1and expand our search to the right half of the array. 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.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.- If the first condition is not true, we update
high = mid -1and search in the left half of array as element at mid is greater than the target. If(Arr[mid] == target)-> If the element is equal, we store its index and continue these steps untillow<=high.
Let us look at the implementation of above approach:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 |
import java.util.*; public class Example { //finds Starting Index or First occurrence of target. static int findStartingIndex(int arr[],int n,int target) { int low = 0; int high = n-1; int index = -1; while(low <= high) { // Calculate mid value. int mid = (low+high)/2; //Condition 1 if(arr[mid]>=target) { high = mid-1; } // Condition 2 : When arr[mid] < target else { low = mid+1; } // Condition 3 if(arr[mid] == target) { index = mid; } } return index; } //finds Last occurrence of target. static int findEndingIndex(int arr[],int n,int target) { int low = 0; int high = n-1; int index = -1; while(low <= high) { // Calculate mid value. int mid = (low+high)/2; //Condition 1 if(arr[mid]<=target) { low = mid+1; } // Condition 2 : When arr[mid] > target else { high = mid-1; } // Condition 3 if(arr[mid] == target) { index = mid; } } return index; } static void findFirstAndLastPosition(int arr[],int n,int target) { int first = findStartingIndex(arr,n,target); int last = findEndingIndex(arr,n,target); System.out.println("The First occurrence of "+target+" at index : "+first+" and the Last occurrence is at index : "+last); } public static void main(String args[]) { int arr[] = new int[]{5,6,6,6,7,8,8,10}; int n = arr.length; int target = 8; findFirstAndLastPosition(arr,n,target); } } |
Output:
|
1 2 3 |
The First occurrence of 8 at index : 5 and the Last occurrence is at index : 6 |
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.
