62. Search in Rotated Sorted Array
A strictly increasing sorted array has been cut at some position and its two parts swapped. Locate the target in this rotated order without restoring or copying the sorted array.
The rotation may be zero. Values are distinct under this contract, so the ambiguous-duplicate variant is a different problem.
Example 1
Input
[4,5,6,7,0,1,2], target=0
Output
4
Explanation: The left side through index 3 is sorted but excludes zero, so search the right side.
Example 2
Input
[3,1], target=2
Output
−1
Explanation: Distinctness permits deciding the sorted singleton/half and shrinking to exhaustion.
Example 3
Input
[MIN,0,MAX], target=MIN
Output
0
Explanation: No rotation and extreme values use the same comparisons.
Constraints
0 <= nums.length <= 105-231 <= nums[i] <= 231 - 1- nums is a rotation of a strictly increasing array; all values are distinct.
Hints
Hint 1
A single rotation introduces only one descending break.
Hint 2
At least one of [left,mid] and [mid,right] is sorted.
Hint 3
Test whether target lies inside the sorted half’s value range, then keep only the possible half.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
Target lies beyond the descending break
[4,5,6,7,0,1,2]
0
4