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

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

###### tags: `leedcode` `python` `medium` `Binary Search`

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

If <code>target</code> is not found in the array, return <code>[-1, -1]</code>.

You mustwrite an algorithm with<code>O(log n)</code> 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:**

- <code>0 <= nums.length <= 10⁵</code>
- <code>-10⁹<= nums[i]<= 10⁹</code>
- <code>nums</code> is a non-decreasing array.
- <code>-10⁹<= target<= 10⁹</code>

## Solution 1 - Binary Search
#### Python

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)

        # find left position
        left, right = 0, n - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] >= target:
                right = mid - 1
            else:
                left = mid + 1
        left_pos = left

        # find right position
        left, right = 0, n - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] > target:
                right = mid - 1
            else:
                left = mid + 1
        right_pos = right

        return [left_pos, right_pos] if left_pos <= right_pos else [-1, -1]

#### C++

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int n = nums.size();

        // find left position
        int left = 0;
        int right = nums.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        int leftPos = left;

        // find right position
        left = 0;
        right = nums.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        int rightPos = right;

        if (leftPos <= rightPos) {
            return {leftPos, rightPos};
        } else {
            return {-1, -1};
        }
    }
};

>### Complexity
>n = nums.length
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(logn) | O(1) |

## Note
一次找一邊