# 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)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://joshualbarb.gitbook.io/leetcode-problems/binary-search/find-first-and-last-position-of-element-in-sorted-array.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.