March 12, 2021

Hello LeetCode enthusiasts π! Today we will be discussing a new problem which uses variation of binary search.

Given an array of integers `nums`

sorted in ascending order, find the starting and ending position of a given `target`

value.

If `target`

is not found in the array, return `[-1, -1]`

.

- 0 β€
`nums.length`

β€ 10^{5} - -10
^{9}β€`nums[i]`

β€ 10^{9} `nums`

is a non-decreasing array.- -10
^{9}β€`target`

β€ 10^{9}

Could you write an algorithm with `O(log n)`

runtime complexity?

Example 1:

```
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
```

Example 2:

```
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
```

Example 3:

```
Input: nums = [], target = 0
Output: [-1,-1]
```

We have a sorted array `nums`

and a `target`

value which we need to search in the array. This description suggests that it is a clear case of ** binary search**. The catch is that the

`target`

can be repeated in the array.Thus, there might be multiple indices where the target can be found. Thus, we need to find these indices. If the element is not found then we should return -1.

We will use binary search algorithm to find the first and last occurrences of the `target`

separately.

- For first occurrence, we will first find the index of the number and then search again in the left subarray as long as we are finding the number.
- For last occurrence, we will first find the index of the number and then search again in the right subarray as long as we are finding the number.

Since we are using binary search which halves the number of elements to be considered after each step, therefore, the time complexity will be ** O(log n)**.

We are not using any data structures for the intermediate calculations, hence the space complexity will be ** O(1)**.

```
public class FindFirstAndLastPositionOfElementInSortedArray {
public int[] searchRange(int[] nums, int target) {
return new int[]{findFirstOccurrence(nums, target), findLastOccurrence(nums, target)};
}
private int findFirstOccurrence(int[] nums, int target) {
// Left and right pointers
int left = 0;
int right = nums.length - 1;
// Index of first occurrence
int firstOccurrence = -1;
// Loop until the two pointers meet
while (left <= right) {
// Middle index
int middle = left + (right - left) / 2;
// Check if we have found the value
if (nums[middle] == target) {
firstOccurrence = middle;
right = middle - 1;
}
// If the target is less than the element
// at the middle index
else if (target < nums[middle]) {
right = middle - 1;
}
// If the target is greater than the element
// at the middle index
else {
left = middle + 1;
}
}
return firstOccurrence;
}
private int findLastOccurrence(int[] nums, int target) {
// Left and right pointers
int left = 0;
int right = nums.length - 1;
// Index of first occurrence
int lastOccurrence = -1;
// Loop until the two pointers meet
while (left <= right) {
// Middle index
int middle = left + (right - left) / 2;
// Check if we have found the value
if (nums[middle] == target) {
lastOccurrence = middle;
left = middle + 1;
}
// If the target is less than the element
// at the middle index
else if (target < nums[middle]) {
right = middle - 1;
}
// If the target is greater than the element
// at the middle index
else {
left = middle + 1;
}
}
return lastOccurrence;
}
}
```

```
def findFirstOccurrence(nums, target):
# Left snd right pointers
left, right = 0, len(nums) - 1
# Index of first occurrence
firstOccurrence = -1
# Loop until the two pointers meet
while left <= right:
# Middle index
middle = left + (right - left) // 2
# Check if we have found the value
if target == nums[middle]:
firstOccurrence = middle
right = middle - 1
# If the target is less than the element
# at the middle index
elif target < nums[middle]:
right = middle - 1
# If the target is greater than the element
# at the middle index
else:
left = middle + 1
return firstOccurrence
def findLastOccurrence(nums, target):
# Left snd right pointers
left, right = 0, len(nums) - 1
# Index of first occurrence
lastOccurrence = -1
# Loop until the two pointers meet
while left <= right:
# Middle index
middle = left + (right - left) // 2
# Check if we have found the value
if target == nums[middle]:
lastOccurrence = middle
left = middle + 1
# If the target is less than the element
# at the middle index
elif target < nums[middle]:
right = middle - 1
# If the target is greater than the element
# at the middle index
else:
left = middle + 1
return lastOccurrence
def searchRange(nums: List[int], target: int) -> List[int]:
return [findFirstOccurrence(nums, target), findLastOccurrence(nums, target)]
```

```
var searchRange = function (nums, target) {
return [findFirstOccurrence(nums, target), findLastOccurrence(nums, target)];
};
const findFirstOccurrence = (nums, target) => {
// Left and right pointers
let left = 0;
let right = nums.length - 1;
// Index of first occurrence
let firstOccurrence = -1;
// Loop until the two pointers meet
while (left <= right) {
// Middle index
let middle = left + parseInt((right - left) / 2);
// Check if we have found the value
if (nums[middle] === target) {
firstOccurrence = middle;
right = middle - 1;
}
// If the target is less than the element
// at the middle index
else if (target < nums[middle]) {
right = middle - 1;
}
// If the target is greater than the element
// at the middle index
else {
left = middle + 1;
}
}
return firstOccurrence;
};
const findLastOccurrence = (nums, target) => {
// Left and right pointers
let left = 0;
let right = nums.length - 1;
// Index of first occurrence
let lastOccurrence = -1;
// Loop until the two pointers meet
while (left <= right) {
// Middle index
let middle = left + parseInt((right - left) / 2);
// Check if we have found the value
if (nums[middle] === target) {
lastOccurrence = middle;
left = middle + 1;
}
// If the target is less than the element
// at the middle index
else if (target < nums[middle]) {
right = middle - 1;
}
// If the target is greater than the element
// at the middle index
else {
left = middle + 1;
}
}
return lastOccurrence;
};
```

```
fun searchRange(nums: IntArray, target: Int): IntArray {
return intArrayOf(findFirstOccurrence(nums, target), findLastOccurrence(nums, target))
}
fun findFirstOccurrence(nums: IntArray, target: Int): Int {
// Left and right pointers
var left = 0
var right = nums.size - 1
// Index of first occurrence
var firstOccurrence = -1
// Loop until the two pointers meet
while (left <= right) {
// Middle index
val middle = left + (right - left) / 2
// Check if we have found the value
when {
nums[middle] == target -> {
firstOccurrence = middle
right = middle - 1
}
target < nums[middle] -> {
right = middle - 1
}
else -> {
left = middle + 1
}
}
}
return firstOccurrence
}
fun findLastOccurrence(nums: IntArray, target: Int): Int {
// Left and right pointers
var left = 0
var right = nums.size - 1
// Index of first occurrence
var lastOccurrence = -1
// Loop until the two pointers meet
while (left <= right) {
// Middle index
val middle = left + (right - left) / 2
// Check if we have found the value
when {
nums[middle] == target -> {
lastOccurrence = middle
left = middle + 1
}
target < nums[middle] -> {
right = middle - 1
}
else -> {
left = middle + 1
}
}
}
return lastOccurrence
}
```

Congratulations π! Today we solved another LeetCode problem which was an extension to the normal binary search.

I hope you enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn, feel free to fork πͺ and star β it.

Till next timeβ¦ Happy coding π and Namaste π!