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.
The essence of this approach is to perform a binary search with a twist, considering the rotation. We first determine which part of the array is sorted: the left or the right. This allows us to intelligently decide where to perform the binary search. If the target lies within the sorted side, we adjust the search range accordingly. Otherwise, we continue the search on the unsorted side, which in the next iteration becomes a new array.
This approach employs a standard binary search. The array is divided based on whether the left or the right half is sorted. If the left part is sorted, we check whether the target falls within that sorted range. If it does, the right boundary is adjusted; otherwise, the search continues in the right half, adjusting the left boundary, and vice versa for the right sorted half.
Time Complexity: O(log n) because each step reduces the search space by half.
Space Complexity: O(1) as no extra space is used aside from variables.
This decomposition-based approach first identifies the pivot index where rotation occurs. Once the break index is acquired, the target search bifurcates: running binary search on subarrays from the determined split point to either the beginning or end of the array.
This solution breaks the problem down by finding a rotation pivot index. The strategy shifts to standard binary search, applied twice on sub-sections of the array pre-determined by the pivot, thus achieving efficiency.
Time Complexity: O(log n) to find the pivot and additional O(log n) for binary search, leading to O(log n) overall.
Space Complexity: O(1) due to in-place operations.
We use binary search to divide the array into two parts, [left,.. mid] and [mid + 1,.. right]. At this point, we can find that one part must be sorted.
Therefore, we can determine whether target is in this part based on the sorted part:
[0,.. mid] form a sorted array:nums[0] leq target leq nums[mid], then our search range can be narrowed down to [left,.. mid];[mid + 1,.. right];[mid + 1, n - 1] form a sorted array:nums[mid] \lt target leq nums[n - 1], then our search range can be narrowed down to [mid + 1,.. right];[left,.. mid].The termination condition for binary search is left geq right. If at the end we find that nums[left] is not equal to target, it means that there is no element with a value of target in the array, and we return -1. Otherwise, we return the index left.
The time complexity is O(log n), where n is the length of the array nums. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
PHP
| Approach | Complexity |
|---|---|
| Binary Search with Rotation Logic | Time Complexity: O(log n) because each step reduces the search space by half. |
| Find Rotated Index and Execute Two Binary Searches | Time Complexity: O(log n) to find the pivot and additional O(log n) for binary search, leading to O(log n) overall. |
| Binary 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 |
Search in rotated sorted array - Leetcode 33 - Python • NeetCode • 517,200 views views
Watch 9 more video solutions →Practice Search in Rotated Sorted Array with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor