LeetCode 33: Search in Rotated Sorted Array Solution
Master LeetCode problem 33 (Search in Rotated Sorted Array), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
33. Search in Rotated Sorted Array
Problem Explanation
Explanation
To solve this problem in O(log n) runtime complexity, we can use a modified binary search algorithm. We can divide the rotated array into two halves. One of the halves must be sorted. We can then check if the target value lies within the sorted half or the unsorted half based on some conditions. We adjust the binary search accordingly based on which half the target value might lie in.
- We compare the target value with the values at the start, middle, and end indices of the array to determine which half is sorted.
- Based on the sorted half, we check if the target value lies within the range of the sorted half. If it does, we perform binary search in that half. Otherwise, we search in the other half.
- We repeat this process until we find the target value or determine that it does not exist in the array.
Time complexity: O(log n) Space complexity: O(1)
Solution Code
class Solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
}
if (nums[left] <= nums[mid]) {
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else {
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 33 (Search in Rotated Sorted Array)?
This page provides optimized solutions for LeetCode problem 33 (Search in Rotated Sorted Array) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 33 (Search in Rotated Sorted Array)?
The time complexity for LeetCode 33 (Search in Rotated Sorted Array) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 33 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 33 in Java, C++, or Python.