28. Search in Rotated Sorted Array
An array of distinct integers was sorted in ascending order and then possibly rotated: some prefix was cut off and moved to the end. For example, [3,7,9,15,18,22] rotated after its third element becomes [15,18,22,3,7,9]. The rotation point is unknown (and there may be no rotation at all).
Given the rotated array nums and an integer target, return the index of target in nums, or -1 if it is not present. Aim for O(log n) time.
Input: nums = [15,18,22,3,7,9], target = 7 Output: 4
Input: nums = [15,18,22,3,7,9], target = 10 Output: -1
Input: nums = [8], target = 8 Output: 0
Constraints
1 <= nums.length <= 5000-10^4 <= nums[i], target <= 10^4- All values in
numsare distinct numsis an ascending array that may have been rotated
💡 Hint 1
Split the array at any index mid. At least one of the two halves is sorted normally. How can you tell which one?
💡 Hint 2
If nums[lo] <= nums[mid], the left half is sorted. Then it is easy to check whether target lies inside its value range.
💡 Hint 3
Keep the half that could contain the target and discard the other, exactly like ordinary binary search.
Try it yourself first ✎
Solutions stick better after a real attempt. Peek when you're ready.
Approach
Run binary search on [lo, hi], but at each step first work out which half is sorted. If nums[lo] <= nums[mid], the left half [lo, mid] is in ascending order: the target is there exactly when nums[lo] <= target < nums[mid], so move hi = mid - 1 in that case and lo = mid + 1 otherwise. If instead the right half [mid, hi] is sorted, check nums[mid] < target <= nums[hi] the same way. Either way half of the window disappears, and the distinct values guarantee the sorted-half test is never ambiguous.
function search(nums, target) {
let lo = 0;
let hi = nums.length - 1;
while (lo <= hi) {
const mid = (lo + hi) >> 1;
if (nums[mid] === target) return mid;
if (nums[lo] <= nums[mid]) {
if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
else lo = mid + 1;
} else {
if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
else hi = mid - 1;
}
}
return -1;
}class 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]) {
if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
else lo = mid + 1;
} else {
if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
else hi = mid - 1;
}
}
return -1;
}
}No submissions yet. Press Submit to run your code against every test.
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
function search(nums, target) {
}Run your code to see results here.