**source:**https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/**C/C++**

**Solution to LeetCode**problem

**34**.

**Find First and Last Position of Element in Sorted Array**.

## Problem

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.

## Examples

**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

We perform two binary searches.

- Binary search to find the minimum index of the target value.
- If there is a minimun index, then we perform a binary search to find the maximum index.
- Because there is a minimum, we can initialize the
`left`

pointer to the first position where the target was found for the first time.

- Because there is a minimum, we can initialize the

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int start = -1;
int end = -1;
int l = 0;
int r = nums.size() - 1;
while (l<=r) {
int m = (l + r) / 2;
if (nums[m] == target) {
start = m;
end = max(end, m);
}
if (nums[m] >= target)
r = m - 1;
else
l = m + 1;
}
if (end != -1) {
l = end;
r = nums.size() - 1;
while (l<=r) {
int m = (l + r) / 2;
if (nums[m] == target)
end = max(end, m);
if (nums[m] <= target)
l = m + 1;
else
r = m - 1;
}
}
return {start, end};
}
};