## Problem

**Problem ID**: 34

**Title**: Find First and Last Position of Element in Sorted Array

**Difficulty**: Medium

**Description**:
Given an array of integers nums sorted in ascending order, find the starting and
ending position of a given target value.

## Thoughts

I have always struggled with implementing binary search well and found this problem very challenging (22 failed submissions).

IMO, The main challenges with implementing binary search are:

- Ensuring that the left and right index are inside the range of the array
- Preventing an infinite loop

## Solution

### Explanation

**First position**: We can think of finding the first position of the element as moving the **right**
pointer **as far left as possible** while the value is more than or equal to the target.
We can achieve this with `m = (l+r)/2`

and `r = m`

. This ensures that the **right**
pointer will always progress towards the left.

**Last Position**: Similarly, the last position of the element is the position of the left pointer
after moving as far right as possible while the value is less than or equal to the
target. We can achieve this with `m = (l+r+1)/2`

and `l = m`

. This ensures that
the **left** pointer will always progress towards the right.

**Preventing infinite loop**: With `l = m + 1`

(first position) and `r = m - 1`

(last position) we can
ensure that the search space will always be reduced when the main pointer is not making any progression.

### Implementation

```
class Solution {
public:
// [1, 2, 3, 3, 3, 4, 5]
int first(const vector<int>& nums, int target) {
int l = 0;
int r = nums.size() - 1;
while (l < r) {
int m = (l+r)/2;
int m_val = nums[m];
if (m_val >= target) {
r = m;
} else {
l = m + 1;
}
}
return nums[r] == target ? l : -1;
}
int last(const vector<int>& nums, int target) {
int l = 0;
int r = nums.size() - 1;
while (l < r) {
int m = (l+r+1)/2;
int m_val = nums[m];
if (m_val <= target) {
l = m;
} else {
r = m -1;
}
}
return nums[l] == target ? l : -1;
}
vector<int> searchRange(vector<int>& nums, int target) {
if (nums.empty()) return {-1, -1};
return {first(nums, target), last(nums,target)};
}
};
```