> For the complete documentation index, see [llms.txt](https://joshualbarb.gitbook.io/leetcode-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://joshualbarb.gitbook.io/leetcode-problems/binary-search/find-first-and-last-position-of-element-in-sorted-array.md).

# Find First and Last Position of Element in Sorted Array

## Problem

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?\ <br>

{% hint style="info" %}
For example:

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

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

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

{% endhint %}

### Thought Process

* To find the first occurence/position of target, if num\[mid] is greater than the target, then we have to move down. Along with this, if num\[mid] is equal to the target, we have to move down because this potentially is not the first position of this element.&#x20;

* To find the last occurence/position of target, if num\[mid] is less than the target then we have to keep moving up. Along with this we have to keep moving up if num\[mid] is equal to target because it potentially may not be the last occurence/position of this element.&#x20;

## Solution

```
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        first = self.first(nums,target)
        last = self.last(nums, target)
          
        return [first,last]
        
    def first(self, nums, target):
        low, high = 0, len(nums)-1
        res = -1
        
        while low <= high:
            mid = low + (high-low)//2
            if nums[mid] >= target:
                high = mid-1
            elif nums[mid] < target:
                low = mid+1
                
            if nums[mid] == target:
                res = mid
        return res
    
    def last(self, nums, target):
        low, high = 0, len(nums)-1
        res = -1
        
        while low <= high:
            mid = low + (high-low)//2
            if nums[mid] <= target:
                low = mid+1
            elif nums[mid] > target:
                high = mid-1
            
            if nums[mid] == target:
                res = mid
            
        return res
```

## Time Complexity

* **Time:** O(log n)
* **Space:** O(1)