# 34. Find First and Last Position of Element in Sorted Array

## Problem Statement

<br>

Given an array of integers `nums` sorted in non-decreasing order, find the starting and ending position of a given `target` value.

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

You must write an algorithm with `O(log n)` runtime complexity.

&#x20;

**Example 1:**

<pre><code><strong>Input: nums = [5,7,7,8,8,10], target = 8
</strong><strong>Output: [3,4]
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: nums = [5,7,7,8,8,10], target = 6
</strong><strong>Output: [-1,-1]
</strong></code></pre>

**Example 3:**

<pre><code><strong>Input: nums = [], target = 0
</strong><strong>Output: [-1,-1]
</strong></code></pre>

&#x20;

**Constraints:**

* `0 <= nums.length <= 105`
* `-109 <= nums[i] <= 109`
* `nums` is a non-decreasing array.
* `-109 <= target <= 109`

## Intuition

```
Approach 2:
Find using BS

Find the position of Left side, if left side exists then only right boundary exixts

Then find this target once for left , Take target +1 for right boundary
Then return ans
```

### Links

<https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/submissions/1052473508/>

### Video Links

### Approach 1:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    int left_index(vector<int>& nums, int target){
        int low=0, high=nums.size()-1;
        while(low<=high){
            int mid = low+(high-low)/2;

            if(nums[mid] == target){
                if(mid == 0)
                    return mid;
                else if(nums[mid] != nums[mid-1])
                    return mid;
                else
                    high = mid-1;
            }
            else if(nums[mid] > target)
                high = mid-1;
            else
                low = mid+1;
        }

        return -1;
    }

    int right_index(vector<int>& nums, int target){
        int low=0, high=nums.size()-1;
        while(low<=high){
            int mid = low+(high-low)/2;

            if(nums[mid] == target){
                if(mid == nums.size()-1)
                    return mid;
                else if(nums[mid] != nums[mid+1])
                    return mid;
                else
                    low = mid+1;
            }
            else if(nums[mid] > target)
                high = mid-1;
            else
                low = mid+1;
        }

        return -1;
    }

    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> ans;
        ans.push_back(left_index(nums,target));
        ans.push_back(right_index(nums,target));

        return ans;
    }
};
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
private:
    int lower_bound(vector<int>& nums, int low, int high, int target){
        while(low <= high){
            int mid = (low + high) >> 1;
            if(nums[mid] < target){
                low = mid + 1;
            }
            else{
                high = mid - 1;
            }
        }
        return low;
    }
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int low = 0, high = nums.size()-1;
        int startingPosition = lower_bound(nums, low, high, target);
        int endingPosition = lower_bound(nums, low, high, target + 1) - 1;
        if(startingPosition < nums.size() && nums[startingPosition] == target){
            return {startingPosition, endingPosition};
        }
        return {-1, -1};
    }
};

```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###


---

# 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://coding-9.gitbook.io/untitled/binary-search/bs-on-1d-array/34.-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.