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

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