*971*

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.

#### Brute Force Method:

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.

#### Efficient Solution:

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.

#### Code:

```
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.