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

🟧 Medium

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.

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

## Solution

My Solution

```go
func SearchRange(nums []int, target int) []int {
    l := LowerBound(nums, target)
    if l == len(nums) || nums[l] != target {
        return []int{-1, -1}
    }

    r := UpperBound(nums, target)
    return []int{l, r - 1}
}

func LowerBound(nums []int, target int) int {
    l, r := 0, len(nums)
    for l < r {
        mid := l + (r-l)/2
        if nums[mid] < target {
            l = mid + 1
        } else {
            r = mid
        }
    }

    return l
}

func UpperBound(nums []int, target int) int {
    l, r := 0, len(nums)
    for l < r {
        mid := l + (r-l)/2
        if nums[mid] <= target {
            l = mid + 1
        } else {
            r = mid
        }
    }

    return l
}
```

### Approach

This solution uses two modified binary searches to find the range:

1. LowerBound (First Position):
   * Uses binary search to find the first occurrence
   * When nums\[mid] == target, continues searching left half
   * Returns leftmost position where target could be inserted
2. UpperBound (Last Position):
   * Uses binary search to find position after last occurrence
   * When nums\[mid] == target, continues searching right half
   * Returns position after the last occurrence
3. Main Function:
   * If LowerBound doesn't find target, return \[-1, -1]
   * Otherwise, return \[LowerBound, UpperBound-1]

### Complexity Analysis

#### Time Complexity: O(log n)

* Performs two binary searches
* Each binary search takes O(log n) time
* Total time is O(log n) + O(log n) = O(log n)

#### Space Complexity: O(1)

* Only uses a constant amount of extra space:
  * Two pointers (left, right)
  * Mid index
  * Result array of size 2

### Why it works

* LowerBound finds first position by treating equal elements as "too big"
* UpperBound finds last position by treating equal elements as "too small"
* Using \[0, len] range instead of \[0, len-1] handles edge cases elegantly
* The difference between < and <= in the two functions is crucial:
  * LowerBound: moves right when element is too small
  * UpperBound: moves right when element is too small OR equal

![result](/files/GGMsKmOehuiTGaHUmmQ0)

Leetcode: [link](https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/description/)


---

# 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://leetcode.realtemirov.uz/problems/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.