Given a sorted array of distinct integers that has been rotated at an unknown pivot index, and an integer target, search for the target in the array. The array may be rotated, meaning it consists of two sorted subarrays. Return the index of the target if it exists, otherwise return -1. The solution must achieve O(log n) time complexity by leveraging a modified binary search approach.
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Explanation: Target 0 is at index 4 in the rotated array.
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
Explanation: Target 3 is not present in the array.
Input: nums = [1], target = 0
Output: -1
The key observation is that after rotation the array consists of two sorted subarrays. At any step of binary search, at least one half of the current interval remains fully sorted. By identifying that sorted half and checking whether the target lies within its bounds, we can discard the other half and continue the search, maintaining the O(log n) time complexity.
left = 0 and right = n - 1.left ≤ right: compute mid = left + (right - left) // 2. If nums[mid] == target, return mid.nums[left] ≤ nums[mid], the left half [left, mid] is sorted. If target lies in [nums[left], nums[mid]), set right = mid - 1; else set left = mid + 1.[mid, right] is sorted. If target lies in (nums[mid], nums[right]], set left = mid + 1; else set right = mid - 1.-1.#include <vector>
using namespace std;
class Solution {
public:
int search(vector& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
if (nums[left] <= nums[mid]) {
if (nums[left] <= target && target < nums[mid])
right = mid - 1;
else
left = mid + 1;
} else {
if (nums[mid] < target && target <= nums[right])
left = mid + 1;
else
right = mid - 1;
}
}
return -1;
}
}; class Solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
if (nums[left] <= nums[mid]) {
if (nums[left] <= target && target < nums[mid])
right = mid - 1;
else
left = mid + 1;
} else {
if (nums[mid] < target && target <= nums[right])
left = mid + 1;
else
right = mid - 1;
}
}
return -1;
}
}def search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
if nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1function search(nums, target) {
let left = 0, right = nums.length - 1;
while (left <= right) {
const mid = left + Math.floor((right - left) / 2);
if (nums[mid] === target) return mid;
if (nums[left] <= nums[mid]) {
if (nums[left] <= target && target < nums[mid])
right = mid - 1;
else
left = mid + 1;
} else {
if (nums[mid] < target && target <= nums[right])
left = mid + 1;
else
right = mid - 1;
}
}
return -1;
}Time Complexity: O(log n) because each iteration halves the remaining search space.
Space Complexity: O(1) as only a constant number of extra variables are used.
Your notes are automatically saved in your browser's local storage and will persist across sessions on this device.