Search in rotated sorted array
MediumUnlock detailed company stats for this questionUpgrade
An array of distinct integers was sorted in ascending order and then rotated at an unknown pivot, so [0, 1, 2, 4, 5, 6, 7] might become [4, 5, 6, 7, 0, 1, 2].
Given the rotated array nums and an integer target, return the index of target in nums, or -1 if it isn't there. Your solution should run in O(log n) time.
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
3 doesn't appear in nums.
Constraints
1 <= nums.length <= 5000-10^4 <= nums[i], target <= 10^4- All values in
numsare distinct.
Approach
A plain binary search doesn't work because the array isn't sorted from end to end. It is sorted in two pieces, though, and any midpoint splits it so that at least one side is fully sorted. Two comparisons tell you whether target lies within a sorted side's range, so at every step you know which half could contain it and can discard the other.
Steps
- Set
left = 0andright = n - 1. - While
left <= right, computemid. Ifnums[mid] == target, returnmid. - If the left half is sorted (
nums[left] <= nums[mid]), search it whennums[left] <= target < nums[mid], and search the right half otherwise. - If the right half is sorted, search it when
nums[mid] < target <= nums[right], and search the left half otherwise. - Return
-1once the range is empty.
Complexity
- Time:
O(log n). Each step halves the search range. - Space:
O(1). You only store a few indices.
Common mistakes
- Writing
nums[left] < nums[mid]instead of<=. Whenleft == mid, the one-element left half is sorted, and the strict check gets it wrong. - Checking
targetagainst only one end of the sorted half. It has to fall between both ends before you can search there.
Interview experiences
1 sharedRelated questions
Squares of sorted arraySort a nearly sorted (or K sorted) array.Find a sorted triplet in a given array.Related courses

Course

Course










