Search in Rotated Sorted Array
MedPrompt
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.
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1Example 3:
Input: nums = [1], target = 0
Output: -1
Constraints:
1 <= nums.length <= 5000-104 <= nums[i] <= 104- All values of
numsare unique. numsis an ascending array that is possibly rotated.-104 <= target <= 104
Approaches
2 approaches with complexity analysis and trade-offs.
The most straightforward approach is to perform a linear scan of the array. We can iterate through each element from the beginning to the end and check if it matches the target value. If a match is found, we return its index. If we traverse the entire array without finding the target, we return -1.
Algorithm
- Initialize a loop counter
ito 0. - Iterate through the
numsarray fromi = 0tonums.length - 1. - In each iteration, check if the current element
nums[i]is equal to thetarget. - If they are equal, the target is found. Return the current index
i. - If the loop completes without finding the target, it means the target is not in the array. Return -1.
Walkthrough
This brute-force method ignores the special properties of the rotated sorted array and treats it like any other unsorted list. It's simple to implement but fails to meet the performance requirements for larger datasets.
class Solution { public int search(int[] nums, int target) { for (int i = 0; i < nums.length; i++) { if (nums[i] == target) { return i; } } return -1; }}Complexity
Time
O(n)
Space
O(1)
Trade-offs
Pros
Very simple to understand and implement.
Works correctly for any array, regardless of its properties.
Cons
Inefficient for large arrays as it may require scanning the entire array.
Does not meet the O(log n) time complexity requirement specified in the problem description.
To achieve the required O(log n) time complexity, we must use a binary search. However, a standard binary search won't work because the array isn't fully sorted. The key observation is that in a rotated sorted array, when you split it at a middle point mid, at least one of the two halves (from left to mid or from mid to right) will always be sorted. We can use this property to our advantage. In each step of the binary search, we identify the sorted half and check if the target lies within its range. If it does, we search within that half; otherwise, we search in the other (potentially unsorted) half. This allows us to discard half of the elements in each iteration, maintaining the O(log n) complexity.
Algorithm
- Initialize two pointers,
left = 0andright = nums.length - 1. - Loop as long as
left <= right. - Calculate the middle index:
mid = left + (right - left) / 2. - If
nums[mid]is thetarget, returnmid. - Determine which half of the array is sorted. The key insight is that at least one half (from
lefttomidormidtoright) must be sorted. - Case 1: The left half (
nums[left]tonums[mid]) is sorted. This is true ifnums[left] <= nums[mid].- Check if the
targetlies within the range of this sorted half (target >= nums[left]andtarget < nums[mid]). - If yes, the target must be in the left half, so update
right = mid - 1. - If no, the target must be in the unsorted right half, so update
left = mid + 1.
- Check if the
- Case 2: The right half (
nums[mid]tonums[right]) is sorted. This is true ifnums[left] > nums[mid].- Check if the
targetlies within the range of this sorted half (target > nums[mid]andtarget <= nums[right]). - If yes, the target must be in the right half, so update
left = mid + 1. - If no, the target must be in the unsorted left half, so update
right = mid - 1.
- Check if the
- If the loop finishes, the
targetwas not found, so return -1.
Walkthrough
This approach adapts the classic binary search algorithm. At each step, we find the middle element. Then, we check if the subarray from left to mid is sorted. If it is, we can easily determine if the target is in this sorted subarray. If the target is in this range, we continue our search in the left half. Otherwise, we search in the right half. If the left subarray is not sorted, it implies the right subarray (from mid to right) must be sorted. We then apply the same logic to the right subarray. This process is repeated until the target is found or the search space is exhausted.
class Solution { public int search(int[] nums, int target) { int left = 0; int right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { return mid; } // Check if the left half (from left to mid) is sorted if (nums[left] <= nums[mid]) { // Check if the target is within the sorted left half if (target >= nums[left] && target < nums[mid]) { right = mid - 1; // Search in the left half } else { left = mid + 1; // Search in the right half } } // Otherwise, the right half (from mid to right) must be sorted else { // Check if the target is within the sorted right half if (target > nums[mid] && target <= nums[right]) { left = mid + 1; // Search in the right half } else { right = mid - 1; // Search in the left half } } } return -1; // Target not found }}Complexity
Time
O(log n)
Space
O(1)
Trade-offs
Pros
Achieves the optimal O(log n) time complexity required by the problem.
Highly efficient for large input arrays.
Solves the problem in a single pass through the binary search loop.
Cons
The logic is more complex to understand and implement correctly compared to a standard binary search or a linear scan.
Solutions
Solution
public class Solution { public int Search(int[] nums, int target) { int n = nums.Length; int left = 0, right = n - 1; while (left < right) { int mid = (left + right) >> 1; if (nums[0] <= nums[mid]) { if (nums[0] <= target && target <= nums[mid]) { right = mid; } else { left = mid + 1; } } else { if (nums[mid] < target && target <= nums[n - 1]) { left = mid + 1; } else { right = mid; } } } return nums[left] == target ? left : -1; }}class Solution {public int search(int[] nums, int target) { int n = nums.length; int left = 0, right = n - 1; while (left < right) { int mid = (left + right) >> 1; if (nums[0] <= nums[mid]) { if (nums[0] <= target && target <= nums[mid]) { right = mid; } else { left = mid + 1; } } else { if (nums[mid] < target && target <= nums[n - 1]) { left = mid + 1; } else { right = mid; } } } return nums[left] == target ? left : -1; }}/** * @param {number[]} nums * @param {number} target * @return {number} */ var search = function (nums, target) { const n = nums.length; let left = 0, right = n - 1; while (left < right) { const mid = (left + right) >> 1; if (nums[0] <= nums[mid]) { if (nums[0] <= target && target <= nums[mid]) { right = mid; } else { left = mid + 1; } } else { if (nums[mid] < target && target <= nums[n - 1]) { left = mid + 1; } else { right = mid; } } } return nums[left] == target ? left : -1; };class Solution {public: int search(vector<int> &nums, int target) { int n = nums.size(); int left = 0, right = n - 1; while (left < right) { int mid = (left + right) >> 1; if (nums[0] <= nums[mid]) { if (nums[0] <= target && target <= nums[mid]) right = mid; else left = mid + 1; } else { if (nums[mid] < target && target <= nums[n - 1]) left = mid + 1; else right = mid; } } return nums[left] == target ? left : -1; }};# below 2 solutions, diff is while condition: left ('<' or '<=') right # I like this better class Solution : def search ( self , nums : List [ int ], target : int ) -> int : n = len ( nums ) left , right = 0 , n - 1 while left <= right : mid = ( left + right ) >> 1 if nums [ mid ] == target : return mid elif nums [ 0 ] <= nums [ mid ]: # left half sorted if nums [ 0 ] <= target <= nums [ mid ]: right = mid - 1 else : left = mid + 1 else : # right half sorted if nums [ mid ] < target <= nums [ n - 1 ]: left = mid + 1 else : right = mid - 1 return - 1 ############ class Solution : def search ( self , nums : List [ int ], target : int ) -> int : n = len ( nums ) left , right = 0 , n - 1 while left < right : mid = ( left + right ) >> 1 if nums [ 0 ] <= nums [ mid ]: # left half sorted if nums [ 0 ] <= target <= nums [ mid ]: right = mid else : left = mid + 1 else : # right half sorted if nums [ mid ] < target <= nums [ n - 1 ]: left = mid + 1 else : right = mid return left if nums [ left ] == target else - 1Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.