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

## Problem Restatement

We are given an integer array `nums` sorted in non-decreasing order and an integer `target`.

We need to find the first and last index where `target` appears.

If `target` does not appear in the array, return:

```python
[-1, -1]
```

The required runtime is `O(log n)`, so we should use binary search instead of scanning the array. The array length can be `0`, and `nums` is sorted in non-decreasing order.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A sorted integer array `nums` and an integer `target` |
| Output | `[first_index, last_index]` |
| If missing | Return `[-1, -1]` |
| Required runtime | `O(log n)` |
| Empty array | Return `[-1, -1]` |

Function shape:

```python
def searchRange(nums: list[int], target: int) -> list[int]:
    ...
```

## Examples

Example 1:

```python
nums = [5, 7, 7, 8, 8, 10]
target = 8
```

The value `8` appears at indices `3` and `4`.

Return:

```python
[3, 4]
```

Example 2:

```python
nums = [5, 7, 7, 8, 8, 10]
target = 6
```

The value `6` does not appear.

Return:

```python
[-1, -1]
```

Example 3:

```python
nums = []
target = 0
```

The array is empty.

Return:

```python
[-1, -1]
```

## First Thought: Linear Search

The simplest approach is to scan the array.

When we first see `target`, record that index as `first`.

Keep scanning until the end. Every time we see `target`, update `last`.

```python
class Solution:
    def searchRange(self, nums: list[int], target: int) -> list[int]:
        first = -1
        last = -1

        for i, num in enumerate(nums):
            if num == target:
                if first == -1:
                    first = i
                last = i

        return [first, last]
```

This is correct, but it takes `O(n)` time.

## Problem With Linear Search

The problem requires `O(log n)` runtime.

A full scan does not use the fact that `nums` is sorted.

Since all occurrences of `target` are grouped together in a sorted array, we can find the boundaries with binary search.

We need two searches:

1. Find the first index where `nums[i] >= target`.
2. Find the first index where `nums[i] > target`.

The first position is the left boundary.

The second position is one step after the right boundary.

## Key Insight

Instead of searching only for equality, search for insertion positions.

For this array:

```python
nums = [5, 7, 7, 8, 8, 10]
target = 8
```

The first index where the value is greater than or equal to `8` is index `3`.

```python
[5, 7, 7, 8, 8, 10]
          ^
```

The first index where the value is greater than `8` is index `5`.

```python
[5, 7, 7, 8, 8, 10]
                ^
```

So the answer is:

```python
[3, 5 - 1] = [3, 4]
```

This boundary-search style is often cleaner than trying to stop when `nums[mid] == target`.

## Algorithm

Write a helper function:

```python
lower_bound(x)
```

It returns the first index `i` such that:

```python
nums[i] >= x
```

If every number is smaller than `x`, it returns `len(nums)`.

Then:

```python
left = lower_bound(target)
right = lower_bound(target + 1) - 1
```

But to avoid relying on `target + 1`, we can write a second boundary search for the first index where:

```python
nums[i] > target
```

This works even at integer limits.

So the plan is:

1. Find `left`, the first index with `nums[i] >= target`.
2. If `left == len(nums)` or `nums[left] != target`, return `[-1, -1]`.
3. Find `right_plus_one`, the first index with `nums[i] > target`.
4. Return `[left, right_plus_one - 1]`.

## Correctness

Because `nums` is sorted, all values smaller than `target` appear before all values equal to `target`.

So the first index where `nums[i] >= target` is exactly the first possible position of `target`.

If this index is outside the array, or if `nums[left]` is not equal to `target`, then `target` does not appear anywhere in the array.

If `target` appears, all copies of `target` form one continuous block.

The first index where `nums[i] > target` is the first position after that block.

Therefore, the last index containing `target` is:

```python
right_plus_one - 1
```

So the algorithm returns exactly the first and last positions of `target`.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(log n)` | We run two binary searches |
| Space | `O(1)` | We only use index variables |

## Implementation

```python
class Solution:
    def searchRange(self, nums: list[int], target: int) -> list[int]:
        def first_greater_or_equal(x: int) -> int:
            left = 0
            right = len(nums)

            while left < right:
                mid = left + (right - left) // 2

                if nums[mid] >= x:
                    right = mid
                else:
                    left = mid + 1

            return left

        def first_greater(x: int) -> int:
            left = 0
            right = len(nums)

            while left < right:
                mid = left + (right - left) // 2

                if nums[mid] > x:
                    right = mid
                else:
                    left = mid + 1

            return left

        left = first_greater_or_equal(target)

        if left == len(nums) or nums[left] != target:
            return [-1, -1]

        right = first_greater(target) - 1

        return [left, right]
```

## Code Explanation

The helper `first_greater_or_equal` searches a half-open range:

```python
[left, right)
```

At the start:

```python
left = 0
right = len(nums)
```

This allows the function to return `len(nums)` when no valid index exists.

For each middle index:

```python
mid = left + (right - left) // 2
```

If `nums[mid] >= x`, then `mid` may be the answer, so we keep the left half including `mid`.

```python
right = mid
```

Otherwise, `nums[mid] < x`, so `mid` cannot be the answer.

```python
left = mid + 1
```

The second helper `first_greater` has the same shape, but its condition is:

```python
nums[mid] > x
```

After finding the left boundary:

```python
left = first_greater_or_equal(target)
```

we check whether `target` actually exists:

```python
if left == len(nums) or nums[left] != target:
    return [-1, -1]
```

Then the right boundary is one index before the first number greater than `target`.

```python
right = first_greater(target) - 1
```

Return both boundaries.

## Testing

```python
def check(nums: list[int], target: int, expected: list[int]) -> None:
    actual = Solution().searchRange(nums, target)
    assert actual == expected, (nums, target, actual, expected)

def run_tests():
    check([5, 7, 7, 8, 8, 10], 8, [3, 4])
    check([5, 7, 7, 8, 8, 10], 6, [-1, -1])
    check([], 0, [-1, -1])
    check([1], 1, [0, 0])
    check([1], 0, [-1, -1])
    check([2, 2, 2, 2], 2, [0, 3])
    check([1, 2, 3, 4, 5], 3, [2, 2])
    check([1, 2, 3, 4, 5], 6, [-1, -1])
    check([-3, -2, -2, -2, 0, 4], -2, [1, 3])

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[5,7,7,8,8,10]`, target `8` | Basic duplicate block |
| `[5,7,7,8,8,10]`, target `6` | Missing target inside value range |
| `[]`, target `0` | Empty array |
| `[1]`, target `1` | Single element found |
| `[1]`, target `0` | Single element missing |
| `[2,2,2,2]`, target `2` | Entire array is target |
| `[1,2,3,4,5]`, target `3` | Single occurrence |
| `[1,2,3,4,5]`, target `6` | Missing target after all values |
| Negative values | Confirms ordinary ordering logic works |