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
PreviewThe 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…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewUse a binary search with pointers l and r. At each iteration, compute mid…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
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 |
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
To iteratively narrow the search space by identifying the sorted half and deciding which half to explore next.
Return -1 When Target is Not Found
To indicate the target does not exist in the array after exhausting the search space.
2 more steps with full analysis available on Pro.
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.
Full line-by-line criticality + rationale for all 16 lines available on Pro.
Test Your Understanding
Why does checking which half is sorted allow the algorithm to discard half the search space correctly?
See the answer with Pro.
Related Problems
Modified 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