Leetcode 0034 First Last Position In Sorted Array
Meta Data
Link
Tags
Similar
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
O(N) Brute Force Linear Search
- Implementation of classic Linear Search Algorithm
O(Log N) Binary Search
- Link
- 5 First and Last occurrence of an Element - YouTube by [[ Aditya Verma ]]
- 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 makinghi = mid - 1
- when
- For Last Occurence
- when
arr[mid] == target
then the next value will be on right side, so makinglo = mid + 1
- when
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;
}
Return to DSA
Notes mentioning this note
There are no notes linking to this note.