A good idea will be to understand this problem statement first. We are given a sorted array and a target element. We need to return the first and last index of this target element in the sorted array. The array has a 0 based indexing, and if the element is not found we need to return a [-1, -1].
Let us look at some sample test cases:
Input: [ 5, 7, 7, 8, 8, 10 ]
Target: 8
Output: [3, 4]
Explanation:
The first occurrence of element 8 is at index 3 and the last occurrence is at index 4
Input: [ 5, 7, 7, 8, 8, 10 ]
Target: 6
Output: [-1, -1]
Explanation:
We cannot find 6 in the array.
The most naive way or the brute force method to solve this problem is very simple. We know the index of each element in the array. So we can devise a way to find the first and last occurrence.
- Start iterating through the array from the beginning and match each element to the target element.
- If the element matches, we get the first index. Mark it and move ahead.
- Keep matching the elements until we see a mismatch.
- This is the last index of the element.
As soon as you have a mismatch, just exit the loop iteration and we have our answer of the first and last index. But this approach is not scalable. In a worst case scenario, we will have to scan the entire array.
In our previous approach, we did not use any extra space, and the time complexity is also O(n). When we think about improving it, we tend to find a logarithmic time complexity. This gives you some idea.
As soon as you see a sorted array, the first thing that should come to your mind is the binary search algorithm. We have to find the first and last index in a sorted array. This is same as searching for that element.
All we have to do is apply a modified version of the binary search algorithm. A traditional approach will be to search for the exact target element. But in this scenario we have to apply this search technique 2 times.
- Find the first occurrence by searching for a the target element such that the left element is smaller or null.
- Find the last occurrence by searching for a target element such that the element to right of it is greater or null.
For example, let us say we have an example array:[0, 0, 1, 1, 2, 3, 5, 5, 5, 5, 5, 5, 5, 5, 7, 7]
Target element = 5
When we start applying binary search for 5, the array will be divided into 2 halves.
The trick here is to now search for an occurrence of 5 with a smaller element to the left in the left half of the array.
Once we get this, repeat the same process to search for an occurrence of 5 with a larger element to the right in the other half.
This is another example of the Divide and Conquer algorithmic paradigm.
public int[] searchRange(int[] nums, int target) {
int left = findLeftBound(nums, target);
int right = findRightBound(nums, target);
return new int[]{left, right};
}
private int findLeftBound(int[] nums, int target) {
int index = -1, low = 0, high = nums.length - 1;
// Standard binary search
while (low <= high) {
int mid = low + (high - low) / 2;
if (nums[mid] == target) {
index = mid;
high = mid - 1; // Look in the left sub-array
}
else if (nums[mid] < target)
low = mid + 1;
else
high = mid - 1;
}
return index;
}
private int findRightBound(int[] nums, int target) {
int index = -1, low = 0, high = nums.length - 1;
// Standard binary search
while (low <= high) {
int mid = low + (high - low) / 2;
if (nums[mid] == target) {
index = mid;
low = mid + 1; // Look in the right sub-array
}
else if (nums[mid] < target)
low = mid + 1;
else
high = mid - 1;
}
return index;
}
Code language: Java (java)Time Complexity: O(\log n)
Space Complexity: O(1)
You can also find the code and test cases on GitHub.
