24. Search in Rotated Sorted Array
nums is a sorted array of distinct values that has been rotated at an unknown pivot. Return the index of target, or -1. Required: O(log n).
Example 1
Input:
nums = [5,6,7,1,2,3], target = 2Output:
4Example 2
Input:
nums = [5,6,7,1,2,3], target = 8Output:
-1Hint 1
At any mid, at least one half is sorted.
Hint 2
Check whether the target lies inside the sorted half; if not, search the other half.
Approach 1: Find pivot, then search
Binary-search the minimum, then a normal binary search on the right part.
⏱ Time O(log n)💾 Space O(1)
Approach 2: One-pass binary search ✅
Decide which half is sorted and whether target falls inside it.
⏱ Time O(log n)💾 Space O(1)
Reference solution for One-pass binary search (time O(log n), space O(1)). Each solution passes every test in all four languages.
class Solution:
def search(self, nums: List[int], target: int) -> int:
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
if nums[lo] <= nums[mid]: # left half is sorted
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else: # right half is sorted
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1class Solution {
public int search(int[] nums, int target) {
int lo = 0, hi = nums.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] == target) return mid;
if (nums[lo] <= nums[mid]) { // left half is sorted
if (nums[lo] <= target && target < nums[mid]) hi = mid - 1; else lo = mid + 1;
} else { // right half is sorted
if (nums[mid] < target && target <= nums[hi]) lo = mid + 1; else hi = mid - 1;
}
}
return -1;
}
}class Solution {
public:
int search(vector<int>& nums, int target) {
int lo = 0, hi = (int)nums.size() - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] == target) return mid;
if (nums[lo] <= nums[mid]) { // left half is sorted
if (nums[lo] <= target && target < nums[mid]) hi = mid - 1; else lo = mid + 1;
} else { // right half is sorted
if (nums[mid] < target && target <= nums[hi]) lo = mid + 1; else hi = mid - 1;
}
}
return -1;
}
};function search(nums, target) {
let lo = 0, hi = nums.length - 1;
while (lo <= hi) {
const mid = (lo + hi) >> 1;
if (nums[mid] === target) return mid;
if (nums[lo] <= nums[mid]) { // left half is sorted
if (nums[lo] <= target && target < nums[mid]) hi = mid - 1; else lo = mid + 1;
} else { // right half is sorted
if (nums[mid] < target && target <= nums[hi]) lo = mid + 1; else hi = mid - 1;
}
}
return -1;
}Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.
This problem is explained in the lesson Binary Search.
Run your code to see results here.