Search in Rotated Sorted Array
Problem
Given an integer array nums sorted in ascending order and rotated at an unknown pivot, and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.
- 1 ≤ nums.length ≤ 5000
- −10⁴ ≤ nums[i] ≤ 10⁴
- All values of nums are unique.
- nums is guaranteed to be rotated at some pivot.
- −10⁴ ≤ target ≤ 10⁴
Example
nums = [4,5,6,7,0,1,2], target = 04The array is rotated at pivot index 3. The algorithm uses a modified binary search to identify which half of the array is sorted at each step. Initially, the left half [4,5,6,7] is sorted. Since target 0 is not in this range, the search moves to the right half [0,1,2]. The process repeats until the target is found at index 4.
Approach
Straightforward Solution
A naive approach is to perform a linear scan, which is O(n) and inefficient for large arrays. A standard binary search fails because the array is not fully sorted.
Core Observation
A rotated sorted array consists of two sorted subarrays. At any point, one half of the current search interval is sorted. This property allows binary search to be adapted by determining which half is sorted and whether the target lies within it.
Path to Optimal
The key recognition signals are 'rotated sorted array' and 'search in O(log n)'. These indicate a Modified Binary Search because the array is partially sorted in two segments. By checking the relative order of nums[l], nums[mid], and nums[r], the algorithm identifies the sorted half and decides which half to discard, maintaining logarithmic time complexity.
Optimal Approach
Use a binary search with pointers l and r. At each iteration, compute mid. If nums[mid] equals target, return mid. Otherwise, check if the left half is sorted (nums[l] <= nums[mid]). If yes, determine if target lies within [nums[l], nums[mid]] to decide which half to search next. If the left half is not sorted, the right half must be sorted, and a similar check is performed. This approach discards half the search space each iteration, guaranteeing O(log n) time.
Time
O(log n)
Each iteration halves the search space by discarding one sorted half, leading to logarithmic time complexity.
Space
O(1)
Only a fixed number of variables (pointers and indices) are used, with no additional data structures.
Pattern Spotlight
Modified Binary Search (Rotated Sorted Array)
At each step, identify which half of the array is sorted, then decide if the target lies within that half; discard the other half to maintain O(log n) search despite rotation.
Solution
| 1 | class Solution:
|
| 2 | def search(self, nums: list[int], target: int) -> int:
|
| 3 | l, r = 0, len(nums) - 1
|
| 4 |
|
| 5 | while l <= r:
|
| 6 | mid = (l + r) // 2
|
| 7 | if nums[mid] == target:
|
| 8 | return mid
|
| 9 |
|
| 10 | if nums[l] <= nums[mid]:
|
| 11 | if target > nums[mid] or target < nums[l]:
|
| 12 | l = mid + 1
|
| 13 | else:
|
| 14 | r = mid - 1
|
| 15 | else:
|
| 16 | if target < nums[mid] or target > nums[r]:
|
| 17 | r = mid - 1
|
| 18 | else:
|
| 19 | l = mid + 1
|
| 20 |
|
| 21 | return -1 |
| 1 | import java.util.*; |
| 2 | |
| 3 | class Solution { |
| 4 | public int search(int[] nums, int target) { |
| 5 | int l = 0, r = nums.length - 1; |
| 6 | |
| 7 | while (l <= r) { |
| 8 | int mid = (l + r) / 2; |
| 9 | if (nums[mid] == target) { |
| 10 | return mid; |
| 11 | } |
| 12 | |
| 13 | if (nums[l] <= nums[mid]) { |
| 14 | if (target > nums[mid] || target < nums[l]) { |
| 15 | l = mid + 1; |
| 16 | } else { |
| 17 | r = mid - 1; |
| 18 | } |
| 19 | } else { |
| 20 | if (target < nums[mid] || target > nums[r]) { |
| 21 | r = mid - 1; |
| 22 | } else { |
| 23 | l = mid + 1; |
| 24 | } |
| 25 | } |
| 26 | } |
| 27 | |
| 28 | return -1; |
| 29 | } |
| 30 | } |
| 1 | #include <vector> |
| 2 | |
| 3 | using namespace std; |
| 4 | |
| 5 | class Solution { |
| 6 | public: |
| 7 | int search(vector<int>& nums, int target) { |
| 8 | int l = 0, r = (int)nums.size() - 1; |
| 9 | |
| 10 | while (l <= r) { |
| 11 | int mid = (l + r) / 2; |
| 12 | if (nums[mid] == target) { |
| 13 | return mid; |
| 14 | } |
| 15 | |
| 16 | if (nums[l] <= nums[mid]) { |
| 17 | if (target > nums[mid] || target < nums[l]) { |
| 18 | l = mid + 1; |
| 19 | } else { |
| 20 | r = mid - 1; |
| 21 | } |
| 22 | } else { |
| 23 | if (target < nums[mid] || target > nums[r]) { |
| 24 | r = mid - 1; |
| 25 | } else { |
| 26 | l = mid + 1; |
| 27 | } |
| 28 | } |
| 29 | } |
| 30 | |
| 31 | return -1; |
| 32 | } |
| 33 | }; |
| 1 | var Solution = function() {}; |
| 2 | |
| 3 | Solution.prototype.search = function(nums, target) { |
| 4 | let l = 0, r = nums.length - 1; |
| 5 | |
| 6 | while (l <= r) { |
| 7 | let mid = Math.floor((l + r) / 2); |
| 8 | if (nums[mid] === target) { |
| 9 | return mid; |
| 10 | } |
| 11 | |
| 12 | if (nums[l] <= nums[mid]) { |
| 13 | if (target > nums[mid] || target < nums[l]) { |
| 14 | l = mid + 1; |
| 15 | } else { |
| 16 | r = mid - 1; |
| 17 | } |
| 18 | } else { |
| 19 | if (target < nums[mid] || target > nums[r]) { |
| 20 | r = mid - 1; |
| 21 | } else { |
| 22 | l = mid + 1; |
| 23 | } |
| 24 | } |
| 25 | } |
| 26 | |
| 27 | return -1; |
| 28 | }; |
Step-by-Step Solution
Initialize Search Boundaries for Binary Search
| 3 | l, r = 0, len(nums) - 1
|
Objective
To set the initial left and right pointers to cover the entire array for binary search.
Key Insight
Starting with l at 0 and r at the last index ensures the entire array is considered. This setup is essential for the binary search to progressively narrow down the search space.
Interview Quick-Check
Core Logic
Initialize pointers to the full array range to begin the binary search.
State & Boundaries
Pointers l and r define the current search interval, which shrinks each iteration.
Perform Modified Binary Search Loop to Locate Target
| 5 | while l <= r:
|
| 6 | mid = (l + r) // 2
|
| 7 | if nums[mid] == target:
|
| 8 | return mid
|
| 10 | if nums[l] <= nums[mid]:
|
| 11 | if target > nums[mid] or target < nums[l]:
|
| 12 | l = mid + 1
|
| 13 | else:
|
| 14 | r = mid - 1
|
| 15 | else:
|
| 16 | if target < nums[mid] or target > nums[r]:
|
| 17 | r = mid - 1
|
| 18 | else:
|
| 19 | l = mid + 1
|
Objective
To iteratively narrow the search space by identifying the sorted half and deciding which half to explore next.
Key Insight
The algorithm leverages the property that one half of the array is sorted. By comparing nums[l], nums[mid], and nums[r], it determines which half is sorted and whether the target lies within that half. This logic allows discarding the other half safely, maintaining O(log n) complexity despite rotation.
Interview Quick-Check
Core Logic
At each iteration, check if nums[mid] is the target; if not, determine which half is sorted and whether the target lies within it to decide the next search boundaries.
State & Boundaries
The loop continues while l <= r, ensuring all possible indices are considered.
Common Pitfalls & Bugs
Incorrectly handling the comparison operators or boundary conditions can cause infinite loops or missed targets.
Return -1 When Target is Not Found
| 21 | return -1 |
Objective
To indicate the target does not exist in the array after exhausting the search space.
Key Insight
Returning -1 after the loop terminates confirms that the target was not found. This is the standard sentinel value for unsuccessful searches.
Interview Quick-Check
Core Logic
Return -1 to signal the absence of the target in the array.
Line Analysis
This solution has 5 Critical lines interviewers watch for.
if nums[mid] == target:Check whether the midpoint value equals the target.
An exact midpoint match solves the search immediately.
return midReturn the midpoint index.
Returning immediately avoids unnecessary further work once the target is found.
if nums[l] <= nums[mid]:Check whether the left half is sorted.
At each step, one half must be sorted; this condition identifies the sorted left half.
else:Enter the branch where the right half is sorted.
If the left half is not sorted, then the right half must be sorted.
return -1Return -1 when the target is absent.
If the interval is exhausted without a match, the target is not present.
mid = (l + r) // 2Compute the midpoint index.
The midpoint splits the rotated array interval for the modified binary search decision.
if target > nums[mid] or target < nums[l]:Determine whether the target is outside the sorted left half.
If the target lies outside the sorted left-half range, the search must continue on the right.
l = mid + 1Move the left pointer to the right half.
Discarding the sorted left half is safe when the target cannot lie inside it.
else:Enter the branch that keeps searching the left half.
Reaching this branch means the target must lie inside the sorted left half.
r = mid - 1Move the right pointer to the left half.
Moving the right pointer left keeps only the part of the sorted left half that can still contain the target.
if target < nums[mid] or target > nums[r]:Determine whether the target is outside the sorted right half.
If the target lies outside the sorted right-half range, the search must move left.
r = mid - 1Move the right pointer to the left half.
Discarding the sorted right half is safe when the target cannot lie inside it.
else:Enter the branch that keeps searching the right half.
Reaching this branch means the target must lie inside the sorted right half.
l = mid + 1Move the left pointer to the right half.
Moving the left pointer right keeps only the part of the sorted right half that can still contain the target.
l, r = 0, len(nums) - 1Initialize the left and right pointers.
Initializing the search boundaries to the full array ensures every index is initially considered.
while l <= r:Binary search while the interval is valid.
The loop continues while the current search interval still contains candidates.
Test Your Understanding
Why does checking which half is sorted allow the algorithm to discard half the search space correctly?
Because in a rotated sorted array, one half is always sorted. If the target lies outside the sorted half's range, it must be in the other half, allowing safe discarding of the sorted half and preserving correctness.
Related Problems
Binary Search pattern
Don't just read it. Drill it.
Reconstruct Search in Rotated Sorted Array from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Search in Rotated Sorted Array drill