*This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful,* *please like**this post and/or* *upvote**my solution post on Leetcode's forums.*

####
Leetcode Problem #34 (*Medium*): Find First and Last Position of Element in Sorted Array

####
*Description:*

*Description:*

(*Jump to*: *Solution Idea* || *Code*: *JavaScript* | *Python* | *Java* | *C++*)

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

.

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

runtime complexity?

####
*Examples:*

*Examples:*

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]

####
*Constraints:*

*Constraints:*

`0 <= nums.length <= 10^5`

`-10^9 <= nums[i] <= 10^9`

`nums`

is a non-decreasing array.`-10^9 <= target <= 10^9`

####
*Idea:*

*Idea:*

(*Jump to*: *Problem Description* || *Code*: *JavaScript* | *Python* | *Java* | *C++*)

This problem is very nearly the definition of a **binary search**. A binary search allows us to find the insertion index for a target number in a sorted array. It's called a "binary" search because in each step it halves the input array and determines in which half the number belongs. Since a binary search is able to eliminate half the remaining array in each iteration, it can accomplish its objective with a **time complexity** of **O(log N)**.

In this case, however, we don't just want to find out where the target number (**T**) would be placed in the nums array (**N**), we want to additionally find out if **T** *actually* exists in **N**, as well as the starting and end indexes.

The standard implementation of a binary search will find the left-most index in which **T** could be placed, though many languages have functions for both sides. Rather than having to define two sets of functions here, however, we can, with a little creativity, use a single function to find our answer.

First, we can perform the standard left binary search (**find**) on **T**. Next, we can easily check to see if **T** exists in **N** already by checking the value stored at the result of that first search (**N[Tleft]**). If we don't find **T** at that index, then **T** does not exist in **N** and we should **return [-1, -1]**.

Otherwise, we still need to find the right end of the range of **T** values in **N**. To do this, we can just use **find** again, this time with the next integer (**T + 1**). Since this will find the index *after* the end of the range of **T** values, we can just move back one position to find the end of the **T** range.

Now that we have our range, we can **return** it.

**Time Complexity: O(log N)**for the binary search**Space Complexity: O(1)**

####
*Implementation:*

*Implementation:*

Python has built-in binary search functions for both sides: **bisect_left()** and **bisect_right()**.

The built-in function for Java, **Arrays.binarySearch()** does not find the left-most insertion point, so it's easier to define our own binary search function.

C++ can use the built-in function **equal_range()**, which returns iterator pointers to the range of T values.

####
*Javascript Code:*

*Javascript Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
var searchRange = function(N, T) {
const find = (target, arr, left=0, right=arr.length) => {
while (left <= right) {
let mid = left + right >> 1
if (arr[mid] < target) left = mid + 1
else right = mid - 1
}
return left
}
let Tleft = find(T, N)
if (N[Tleft] !== T) return [-1,-1]
return [Tleft, find(T+1, N, Tleft) - 1]
};
```

####
*Python Code:*

*Python Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

#####
*w/ bisect_left() & bisect_right():*

*w/ bisect_left() & bisect_right():*

```
class Solution:
def searchRange(self, N: List[int], T: int) -> List[int]:
Tleft = bisect_left(N, T)
if Tleft == len(N) or N[Tleft] != T: return [-1, -1]
return [Tleft, bisect_right(N, T) - 1]
```

#####
*w/ Custom Binary Search:*

*w/ Custom Binary Search:*

```
class Solution:
def searchRange(self, N: List[int], T: int) -> List[int]:
def find(target, arr, left=0):
right = len(arr) - 1
while left <= right:
mid = left + right >> 1
if arr[mid] < target: left = mid + 1
else: right = mid - 1
return left
Tleft = find(T, N)
if Tleft == len(N) or N[Tleft] != T: return [-1, -1]
return [Tleft, find(T+1, N, Tleft) - 1]
```

####
*Java Code:*

*Java Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

```
class Solution {
public int[] searchRange(int[] N, int T) {
int Tleft = find(T, N, 0);
if (Tleft == N.length || N[Tleft] != T) return new int[] {-1, -1};
return new int[] {Tleft, find(T+1, N, Tleft) - 1};
}
public int find(int target, int[] arr, int left) {
int right = arr.length - 1;
while (left <= right) {
int mid = left + right >> 1;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return left;
}
}
```

####
*C++ Code:*

*C++ Code:*

(*Jump to*: *Problem Description* || *Solution Idea*)

#####
*w/ equal_range():*

*w/ equal_range():*

```
class Solution {
public:
vector<int> searchRange(vector<int>& N, int T) {
pair<vector<int>::iterator,vector<int>::iterator> range;
range = equal_range(N.begin(), N.end(), T);
int Tleft = distance(N.begin(), range.first);
if (Tleft == N.size() || N[Tleft] != T) return {-1, -1};
return {Tleft, (int)distance(N.begin(), range.second) - 1};
}
};
```

#####
*w/ Custom Binary Search:*

*w/ Custom Binary Search:*

```
class Solution {
public:
vector<int> searchRange(vector<int>& N, int T) {
int Tleft = find(T, N);
if (Tleft == N.size() || N[Tleft] != T) return {-1, -1};
return {Tleft, find(T+1, N, Tleft) - 1};
}
int find(int target, vector<int> arr, int left=0) {
int right = arr.size() - 1;
while (left <= right) {
int mid = left + right >> 1;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return left;
}
};
```

## Top comments (0)