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 <= 104The key challenge in Search in Rotated Sorted Array is that the array was originally sorted but then rotated at some pivot. A naive linear scan would work, but it does not take advantage of the array's structure. Instead, the optimal strategy adapts binary search.
During each step of binary search, you check which half of the array is still sorted. Because a rotated array always has at least one sorted half, you can determine whether the target lies within that sorted segment or in the other half. By adjusting the search boundaries accordingly, you progressively narrow down the range.
This approach preserves the logarithmic efficiency of binary search. The algorithm repeatedly compares the mid element with the left and right boundaries to identify the sorted portion and decide the next search direction.
The result is an efficient search with O(log n) time complexity and constant O(1) space usage.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Modified Binary Search | O(log n) | O(1) |
NeetCode
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.
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.
1#include <stdio.h>
2int search(int* nums, int numsSize, int target) {
3 int left = 0, right = numsSize - 1This 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.
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.
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.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem is frequently asked in FAANG and other top tech company interviews. It tests understanding of binary search variations, edge cases, and the ability to reason about partially sorted data.
Binary search works because even after rotation, at least one half of the array remains sorted at every step. By identifying the sorted half and checking if the target lies within it, you can safely eliminate half the search space.
An array combined with the binary search technique is the best choice. The algorithm relies on index-based access to efficiently divide the search space and identify sorted segments.
The optimal approach uses a modified binary search. At each step, determine which half of the array is sorted and check if the target lies within that range, then continue searching in the appropriate half. This keeps the time complexity at O(log n).
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.