## Algorithm

Problem Name: 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`

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
int* searchRange(int* nums, int numsSize, int target, int* returnSize) {
int i, j, *range;
int start, end, mid;

range = malloc(2 * sizeof(int));
//assert(range);

i = j = -1;
start = 0; end = numsSize - 1;
while (start  < = end) {
mid = start + (end - start) / 2;
if (nums[mid] == target) {
i = j = mid;
while (i > 0 && nums[i - 1] == target) {
i --;
}
while (j  <  numsSize - 1 && nums[j + 1] == target) {
j ++;
}
break;
} else if (nums[mid]  <  target) {
start = mid + 1;
} else {
end = mid - 1;
}
}

range[0] = i;
range[1] = j;

*returnSize = 2;

return range;
}
``````
Copy The Code &

Input

cmd
nums = [5,7,7,8,8,10], target = 8

Output

cmd
[3,4]

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int lo = lower_bound(nums.begin(), nums.end(), target) - nums.begin();
int hi = upper_bound(nums.begin(), nums.end(), target) - nums.begin() - 1;
if(lo > hi) return {-1,-1};
return {lo, hi};
}
};

``````
Copy The Code &

Input

cmd
nums = [5,7,7,8,8,10], target = 6

Output

cmd
[-1,-1]

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public int[] searchRange(int[] nums, int target) {
return new int[]{binarySearchHelper(nums, target, -1), binarySearchHelper(nums, target, 1)};
}

private int binarySearchHelper(int[] nums, int target, int direction) {
int idx = -1;
int start = 0;
int end = nums.length - 1;
while (start  < = end) {
int mid = (start + end) / 2;
if (nums[mid] == target) {
idx = idx == -1 ? mid : (direction == -1 ? Math.min(mid, idx) : Math.max(mid, idx));
if (direction == -1) {
end = mid - 1;
} else {
start = mid + 1;
}
} else if (nums[mid] > target) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return idx;
}
}
``````
Copy The Code &

Input

cmd
nums = [], target = 0

Output

cmd
[-1,-1]

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution(object):
def searchRange(self, nums, target):
l, r = bisect.bisect_left(nums, target), bisect.bisect_right(nums, target) - 1
return [l, r] if 0 <= l <= r else [-1, -1]
``````
Copy The Code &

Input

cmd
nums = [5,7,7,8,8,10], target = 6

Output

cmd
[-1,-1]

### #6 Code Example with C# Programming

```Code - C# Programming```

``````
namespace LeetCode
{
public class _034_SearchForARange
{
public int[] SearchRange(int[] nums, int target)
{
int lo = 0, hi = nums.Length - 1, mid;
while (lo  < = hi)
{
mid = lo + (hi - lo) / 2;
if (target > nums[mid])
lo = mid + 1;
else
hi = mid - 1;
}
if (lo == nums.Length || nums[lo] != target)
return new int[] { -1, -1 };

var result = new int[2];
result[0] = lo;

lo = 0; hi = nums.Length - 1;
while (lo  < = hi)
{
mid = lo + (hi - lo) / 2;
if (target >= nums[mid])
lo = mid + 1;
else
hi = mid - 1;
}
result[1] = lo - 1;

return result;
}
}
}
``````
Copy The Code &

Input

cmd
nums = [], target = 0

Output

cmd
[-1,-1]