Solution: Find First and Last Position of Element in Sorted Array
Tags: algorithms, javascript, java, python
Published: 2021-04-29 09:23:56

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/discuss/1181832).*

---

#### [Leetcode Problem #34 (*Medium*): Find First and Last Position of Element in Sorted Array](https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
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:***
>
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:***
>
 - `0 <= nums.length <= 10^5`
 - `-10^9 <= nums[i] <= 10^9`
 - `nums` is a non-decreasing array.
 - `-10^9 <= target <= 10^9`

---

#### ***Idea:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

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:***

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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))

##### ***w/ bisect_left() & bisect_right():***
```python
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:***
```python
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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))

##### ***w/ equal_range():***
```c++
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:***
```c++
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;
    }
};
```