1. Find the first and last position of a element in sorted array:
In this problem, they will gave us a sorted array and a number. We have to find out the first and last position of that element.
if the target is not found, we have to return [-1,-1]. We have to solve this problem in O(log_n) time. So, we have to use binary search algorithm.
Input: nums = [5 ,7 ,7, 8, 9, 10], target=7
Output: [1, 2]
Solution:
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int st=0,en=nums.size()-1;
int index1=-1,index2=-1;
while(st<=en){
int mid = st + (en-st)/2;
if(nums[mid]>target) en = mid-1;
else if(nums[mid]<target) st = mid+1;
else if(nums[mid]==target){
index1 = mid;
en = mid-1;
}
}
int st1=0,en1=nums.size()-1;
while(st1<=en1){
int mid = st1 + (en1-st1)/2;
if(nums[mid]>target) en1 = mid-1;
else if(nums[mid]<target) st1 = mid+1;
else if(nums[mid]==target){
index2 = mid;
st1 = mid+1;
}
}
return {index1,index2};
}
};
Time complexity: O(log_n)
2. Search Insert Position:
Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
Input: nums = [1,3,5,6], target = 5
Output: 2
Solution:
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int st=0,en=nums.size()-1;
int in = -1;
while(st<=en){
int mid = st + (en-st) /2;
if(nums[mid]==target){
return mid;
break;
}
else if(nums[mid]>target) en = mid-1;
else if(nums[mid]<target) st = mid+1;
}
return st;
}
};
Time complexity: O(log_n)
Problem Link: Search Insert Position - LeetCode
Comments
Post a Comment