Search in Rotated Sorted Array Leetcode Solution
Search in Rotated Sorted Array Leetcode Problem :
There is an integer array nums sorted in ascending order (with distinct values).
Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]] (0-indexed).
For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].
Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.
You must write an algorithm with O(log n) runtime complexity.
Search in Rotated Sorted Array Leetcode Problem Solution :
Constraints :
- 1 <= nums.length <= 5000
- -10^4 <= nums[i] <= 10^4
- All values of nums are unique.
- nums is an ascending array that is possibly rotated.
- -10^4 <= target <= 10^4
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
Example 2:
Input: nums = [1], target = 0
Output: -1
Idea:
The given problem asks us to find the index of the target element in the given rotated sorted array.
Approach:
The solution provided in the code implements, Binary search.
The Binary search approach is based on the fact that a rotated sorted array can be divided into two sorted arrays.
The approach starts with finding the mid element and compares it with the target element.
If they are equal, it returns the mid index. If the left half of the array is sorted, then it checks if the target lies between the start and the mid, and updates the end pointer accordingly.
Otherwise, it checks if the target lies between mid and end, and updates the start pointer accordingly.
If the right half of the array is sorted, then it checks if the target lies between mid and end, and updates the start pointer accordingly.Otherwise, it checks if the target lies between start and mid, and updates the end pointer accordingly.
This process continues until the target element is found, or the start pointer becomes greater than the end pointer, in which case it returns -1.This approach has a time complexity of O(log n).
Complexity:
Time Complexity:
Time complexity of the Binary search approach is O(log n), where n is the size of the input array.Space Complexity:
Space complexity of both approaches is O(1) as we are not using any extra space to store any intermediate results.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
class Solution {
public:
int search(vector< int>& nums, int target) {
int start=0,end=nums.size()-1;
int mid= (start+end)/2;
while(start<=end){
mid=(start+end)/2;
if(target==nums[mid]){
return mid;
}
if(nums[start]<=nums[mid]){
if(nums[start]<=target && nums[mid]>=target){
end=mid-1;
}
else{
start=mid+1;
}
}
else{
if(nums[end]>=target && nums[mid]<=target){
start=mid+1;
}
else{
end=mid-1;
}
}
}
return -1;
}
};
class Solution {
public int search(int[] nums, int target) {
int start = 0, end = nums.length - 1;
int mid = (start + end) / 2;
while (start <= end) {
mid = (start + end) / 2;
if (target == nums[mid]) {
return mid;
}
if (nums[start] <= nums[mid]) {
if (nums[start] <= target && nums[mid] >= target) {
end = mid - 1;
} else {
start = mid + 1;
}
} else {
if (nums[end] >= target && nums[mid] <= target) {
start = mid + 1;
} else {
end = mid - 1;
}
}
}
return -1;
}
}class Solution:
def search(self, nums, target):
start, end = 0, len(nums) - 1
mid = (start + end) / 2
while start <= end:
mid = (start + end) / 2
if target == nums[mid]:
return mid
if nums[start] <= nums[mid]:
if nums[start] <= target and nums[mid] >= target:
end = mid - 1
else:
start = mid + 1
else:
if nums[end] >= target and nums[mid] <= target:
start = mid + 1
else:
end = mid - 1
return -1
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment