Problem
Given an integer array nums that was originally sorted in ascending order and then possibly rotated, along with an integer target, return the index of target if it exists. Otherwise, return -1.You may assume that all elements in the array are distinct. The algorithm should run in
O(log n) time.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
nums = [4,5,6,7,0,1,2]
target = 0 Output
4 Solution
This solution uses a modified Binary Search. Even though the array is rotated, at least one half of the array is always sorted.For each middle element, we first check whether the target is present at
mid. If it is, we return the index immediately.
If the target is not found, we determine which half of the current search range is sorted. If the left half is sorted, we check whether the target lies within its range. If it does, we recursively search the left half; otherwise, we search the right half.
If the right half is sorted, we similarly check whether the target lies within its range. If it does, we recursively search the right half; otherwise, we search the left half.
The process continues recursively until the target is found or the search range becomes empty.
class Solution {
public int search(int[] nums, int target) {
return binarySearch(nums, target, 0, nums.length - 1);
}
public int binarySearch(int[] nums, int target, int left, int right) {
if (left > right)
return -1;
int mid = left + (right - left) / 2;
if (target == nums[mid])
return mid;
// Left half is sorted.
if (nums[left] <= nums[mid]) {
if (target >= nums[left] && target < nums[mid]) {
return binarySearch(nums, target, left, mid - 1);
} else {
return binarySearch(nums, target, mid + 1, right);
}
} else {
// Right half is sorted.
if (target > nums[mid] && target <= nums[right]) {
return binarySearch(nums, target, mid + 1, right);
} else {
return binarySearch(nums, target, left, mid - 1);
}
}
}
}Complexity
Each recursive call eliminates approximately half of the remaining search space, resulting in a time complexity ofO(log n).
Because the solution uses recursion, the extra space complexity is
O(log n) due to the recursive call stack.