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

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`

**Problem Analysis:**

Because the nums is sorted, so we can use bisection method to find the first index that equal the target, then first index that greater the target. So it is the range value we wanted.

If you are familiar with c++ stl, you can imitate the lower_bound and upper_bound to get the range.

**Solution**

`class Solution {`

public:

vector<int> searchRange(vector<int>& nums, int target) {

int start = 0;

int len = nums.size();

while (len > 0) {

int half = len >> 1;

int mid = start + half;

if (nums[mid] < target) {

start = mid + 1;

len = len - half - 1;

} else {

len = half;

}

}

if (start == nums.size() || nums[start] != target) return {-1, -1};

int end = 0;

len = nums.size() ;

while (len > 0) {

int half = len >> 1;

int mid = end + half;

if (nums[mid] > target) {

len = half;

} else {

end = mid + 1;

len = len - half - 1;

}

}

return {start, end - 1};

}

};

time complexity is O(log)

Space complexity is O(1)