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

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

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 <= 105`
• `-109 <= nums[i] <= 109`
• `nums` is a non-decreasing array.
• `-109 <= target <= 109`

class Solution
{
public:
vector<int> searchRange(vector<int> &A, int target)
{
int n = A.size();
int i = 0, j = n - 1;
vector<int> ret(2, -1);
if (n == 0)
return ret;
while (i < j)
{
int mid = (i + j) / 2;
if (A[mid] < target)
i = mid + 1;
else
j = mid;
}
if (A[i] != target)
return ret;
else
ret = i;

j = n - 1;
while (i < j)
{
int mid = (i + j) / 2 + 1;
if (A[mid] > target)
j = mid - 1;
else
i = mid;
}
ret = j;
return ret;
}
};