Watch 10 video solutions for Search in Rotated Sorted Array, a medium level problem involving Array, Binary Search. This walkthrough by NeetCode has 517,200 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3 Output: -1
Example 3:
Input: nums = [1], target = 0 Output: -1
Constraints:
1 <= nums.length <= 5000-104 <= nums[i] <= 104nums are unique.nums is an ascending array that is possibly rotated.-104 <= target <= 104Problem Overview: You get a sorted array that has been rotated at an unknown pivot. The order is still increasing on each side of the pivot. Your task is to find the index of a target value in O(log n) time. If the target does not exist, return -1.
Approach 1: Linear Scan (O(n) time, O(1) space)
The simplest approach is to iterate through the array and compare each element with the target. The moment you find a match, return its index. If the loop finishes without a match, return -1. This ignores the sorted property entirely and works for any array. While easy to implement, it runs in O(n) time, which fails the logarithmic time expectation usually implied in interview settings.
Approach 2: Binary Search with Rotation Logic (O(log n) time, O(1) space)
This approach modifies standard binary search. Even though the array is rotated, at least one half of the array remains sorted at any moment. Compute mid. If nums[mid] equals the target, return it immediately. Otherwise check whether the left half (nums[left]..nums[mid]) is sorted. If it is, verify whether the target lies inside that range and adjust right. If not, move left to the other half. If the right half is sorted, perform the symmetric check. This keeps halving the search space while respecting the rotation property.
Approach 3: Find Rotation Index then Binary Search (O(log n) time, O(1) space)
This method separates the problem into two steps. First, locate the rotation pivot using binary search. The pivot is the smallest element where the order breaks. Once you know the pivot, the array effectively becomes two sorted segments. Decide which segment could contain the target by comparing it with boundary values, then run a normal binary search on that half. This approach explicitly identifies the rotation structure, which some developers find easier to reason about when working with array transformations.
Recommended for interviews: The modified binary search with rotation logic is the expected solution. It keeps the implementation compact while maintaining O(log n) time. Explaining the linear scan briefly shows baseline reasoning, but demonstrating the rotated binary search proves you understand how sorted structure enables logarithmic search.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Linear Scan | O(n) | O(1) | Quick brute-force check or when input size is very small |
| Binary Search with Rotation Logic | O(log n) | O(1) | General optimal solution expected in coding interviews |
| Find Pivot then Binary Search | O(log n) | O(1) | Useful when you want a clear pivot-based reasoning for rotated arrays |