The goal is to find the target's index in a rotated sorted array. Start by applying a modified binary search that accounts for the unknown pivot. By checking which half of the array is properly sorted and narrowing the search accordingly, you can achieve O(log n) time complexity while avoiding unnecessary linear scans.
Problem Statement
You are given an integer array nums that was originally sorted in ascending order but might have been rotated at an unknown pivot. The rotation shifts elements so that the array may look like [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]].
Given this possibly rotated array nums and an integer target, return the index of target if it exists in nums; otherwise, return -1. Your solution must efficiently search without scanning every element.
Examples
Example 1
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example details omitted.
Example 2
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
Example details omitted.
Example 3
Input: nums = [1], target = 0
Output: -1
Example details omitted.
Constraints
- 1 <= nums.length <= 5000
- -104 <= nums[i] <= 104
- All values of nums are unique.
- nums is an ascending array that is possibly rotated.
- -104 <= target <= 104
Solution Approach
Identify Sorted Half
At each binary search step, determine whether the left or right half of the current segment is sorted. This ensures you can rule out halves where the target cannot reside, respecting the rotated structure.
Adjust Search Range
Compare the target to the sorted half's boundaries. If the target lies within this half, continue the search there; otherwise, shift to the other half. Repeat until the target is found or the search space is empty.
Return Result
If the search concludes without locating the target, return -1. Otherwise, return the index identified during binary search, ensuring correctness even when the pivot divides the array.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity is O(log n) because each step halves the search space, and space complexity is O(1) if iterative, or O(log n) if recursion is used for binary search.
What Interviewers Usually Probe
- Ask why a standard binary search fails on rotated arrays.
- Probe understanding of identifying sorted segments versus pivoted segments.
- Check if candidate can maintain O(log n) efficiency despite rotation.
Common Pitfalls or Variants
Common pitfalls
- Attempting simple binary search without handling rotation leads to incorrect indices.
- Failing to correctly identify which half is sorted can skip the target unintentionally.
- Overlooking edge cases where the pivot is at the array start or end causes off-by-one errors.
Follow-up variants
- Searching in a rotated sorted array with duplicate values requires additional checks to skip equal elements.
- Finding the minimum element index in a rotated array leverages similar pivot detection logic.
- Counting occurrences of a target in a rotated sorted array extends the pattern to handle multiple identical elements.
How GhostInterview Helps
- Guides step-by-step through the binary search adjustment for pivoted arrays, highlighting common failure modes.
- Offers hints for segment comparison and boundary checks to maintain O(log n) efficiency.
- Provides practice on edge cases, like single-element arrays or rotations at array boundaries, to solidify the pattern.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
Why can't I use regular binary search for Search in Rotated Sorted Array?
Regular binary search assumes a fully sorted array. Rotations break this order, so you must check which half is sorted at each step.
How do I determine which side of the array is properly sorted?
Compare the start, middle, and end values. The half where start <= middle (or middle <= end) is sorted, guiding where the target may exist.
What is the time complexity for this pattern?
The modified binary search maintains O(log n) because each iteration halves the search space, despite rotation.
Can this approach handle arrays of length 1?
Yes, the binary search logic still applies. If the single element equals the target, return 0; otherwise, return -1.
What if the array contains duplicates?
Duplicates require extra checks to skip equal elements since the sorted-half detection may be ambiguous; otherwise, the pattern remains similar.
Need direct help with Search in Rotated Sorted Array instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Search in Rotated Sorted Array from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Locate the first and last index of a target in a sorted array using binary search for precise O(log n) performance.
Open problem page#35 Search Insert PositionFind the correct index for a target value in a sorted array using binary search, or return the position where it should be inserted.
Open problem page#4 Median of Two Sorted ArraysFind the median of two sorted arrays using binary search for efficient O(log(min(m, n))) time complexity.
Open problem page