Problem
You are given an integer array sorted ascending then rotated at some pivot. Find the index of target in O(log n).
Example
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4Solution
Modified binary search. At each step, identify which half is sorted and check if target is in that half.
def search(nums, target):
l, r = 0, len(nums) - 1
while l <= r:
mid = (l + r) // 2
if nums[mid] == target: return mid
if nums[l] <= nums[mid]:
if nums[l] <= target < nums[mid]: r = mid - 1
else: l = mid + 1
else:
if nums[mid] < target <= nums[r]: l = mid + 1
else: r = mid - 1
return -1function search(nums, target) {
let l = 0, r = nums.length - 1;
while (l <= r) {
const mid = Math.floor((l + r) / 2);
if (nums[mid] === target) return mid;
if (nums[l] <= nums[mid]) {
if (nums[l] <= target && target < nums[mid]) r = mid - 1;
else l = mid + 1;
} else {
if (nums[mid] < target && target <= nums[r]) l = mid + 1;
else r = mid - 1;
}
}
return -1;
}int search(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (nums[mid] == target) return mid;
if (nums[l] <= nums[mid]) {
if (nums[l] <= target && target < nums[mid]) r = mid - 1;
else l = mid + 1;
} else {
if (nums[mid] < target && target <= nums[r]) l = mid + 1;
else r = mid - 1;
}
}
return -1;
}public int search(int[] nums, int target) {
int l = 0, r = nums.length - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (nums[mid] == target) return mid;
if (nums[l] <= nums[mid]) {
if (nums[l] <= target && target < nums[mid]) r = mid - 1;
else l = mid + 1;
} else {
if (nums[mid] < target && target <= nums[r]) l = mid + 1;
else r = mid - 1;
}
}
return -1;
}Complexity
- Time: O(log n)
- Space: O(1)
Explanation
In a rotated sorted array, at any midpoint, at least one half is fully sorted. Determine which, then check if target lies within it.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?