# Leetcode 0034 First Last Position In Sorted Array

## Problem Statement

• 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

``````
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Input: nums = [], target = 0
Output: [-1,-1]

``````

## Solution Approaches

• Basically Binary search except we are not returning, instead storing the value and running the loop again
• For First Occurrence
• when `arr[mid] == target` then the next value will be on left side, so making `hi = mid - 1`
• For Last Occurence
• when `arr[mid] == target` then the next value will be on right side, so making `lo = mid + 1`
``````
vector<int> searchRange(vector<int>& nums, int target) {
vector<int> ans;

int lo = 0;
int hi = nums.size() - 1;
int mid;
int pos = -1;

// first occurence
while (lo <= hi) {
mid = lo + (hi - lo) / 2;

if (nums[mid] == target) {
pos = mid;
hi = mid - 1;
}
else if (nums[mid] > target) {
hi = mid - 1;
} else {
lo = mid + 1;
}
}

ans.push_back(pos);

// last occurence
lo = mid;
hi = nums.size() - 1;
pos = -1;
while (lo <= hi) {
mid = lo + (hi - lo) / 2;

if (nums[mid] == target) {
pos = mid;
lo = mid + 1;
}
else if (nums[mid] > target) {
hi = mid - 1;
} else {
lo = mid + 1;
}
}
ans.push_back(pos);

return ans;
}

``````