LeetCode Find First and Last Position of Element in Sorted Array Solution Explained - C++

The solution to LeetCode problem - Find First and Last Position of Element in Sorted Array. We modify the Binary Search in this problem and search the left subarray in case we find the target in the middle. To find the last position, we search the right subarray in case the target is found in the middle.

Time Complexity - O(log N)
Space Complexity - O(1)

You can follow me on:-

[madhurjyadeka]

@AnimeshGaitonde I wanna ask if I'm given the array of 5, 7, 7, 8, 8, 8, 8, 10 and the target is 8 then ..the values returned should be the value of indices viz [3, 4, 5, 6] but according to your program the result we will get is [3, 3] . Am I wrong ?? plz reply to this thread.

[rahuljha]

Time limit exceeded. Plz provide correct solution.

[cat-codeson]

Bro baar baar time limit exceede aa jaa rha hai please helpl
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
vector<int>result;
int firstIndex= firstOcc(nums, target);
int lastIndex = lastOcc(nums, target);

result.push_back(lastIndex);
return result;

}
int firstOcc(vector<int>& nums, int target){
int start = 0;
int end = nums.size()-1;
int mid;
int ans = -1;
while(start <= end){
mid = end - (start+end)/2;

if(target==nums[mid]){
ans = mid;
end = mid-1;
}
else if(target >nums[mid]){
start = mid+1;
}
else{
end = mid-1;
}
// mid=end-(start+end)/2;
}
return ans;
}
int lastOcc(vector<int>& nums, int target){
int start = 0;
int end = nums.size()-1;
int ans = -1;
int mid;
while(start <= end){
mid = end - (start+end)/2;

if(target == nums[mid]){
ans = mid;
start = mid+1;
}
else if(target > nums[mid]){
start = mid+1;
}
else{
end = mid-1;
}
// mid = end - (start+end)/2;
}
return ans;

}
};