Search in Rotated Sorted Array
Find a target in a rotated increasing array of distinct values, using logarithmic time.
Work through the cases
3 examplesInput notation
Space-separated integers on line 1. Target on line 2.Expected result
The zero-based index, or -1.Case 1
Input
6 8 1 3 4 3
Expected output
3
Case 2
Input
5 1 2 7
Expected output
-1
Case 3
Input
1 1
Expected output
0
These notes use simplified input/output notation. The linked platform defines the method signature and judge format.
FROM IDEA TO IMPLEMENTATION
Understand the approach.
Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.
The first idea is a left-to-right scan. Correct, but n ≤ 5000 and the problem requires O(log n). After the rotation the array is no longer fully sorted, so ordinary binary search cannot tell which half holds target. The key is that any cut leaves at least one half monotonic. Comparing nums[0] with nums[mid] tells us whether the left half is sorted; then we check whether target lies in that sorted range and discard the other half. So we can still binary-search: the sorted half decides keep-or-drop, and the unsorted half is cut again in the next round.
We use binary search to divide the array into two parts, [left,.. mid] and [mid + 1,.. right]. At this point, we can find that one part must be sorted.
Therefore, we can determine whether target is in this part based on the sorted part:
- If the elements in the range [0,.. mid] form a sorted array: - If nums[0] ≤ target ≤ nums[mid], then our search range can be narrowed down to [left,.. mid]; - Otherwise, search in [mid + 1,.. right]; - If the elements in the range [mid + 1, n - 1] form a sorted array: - If nums[mid] \lt target ≤ nums[n - 1], then our search range can be narrowed down to [mid + 1,.. right]; - Otherwise, search in [left,.. mid].
The termination condition for binary search is left ≥ right. If at the end we find that nums[left] is not equal to target, it means that there is no element with a value of target in the array, and we return -1. Otherwise, we return the index left.
The time complexity is O(log n), where n is the length of the array nums. The space complexity is O(1).
class Solution {
public int search(int[] nums, int target) {
int n = nums.length;
int left = 0, right = n - 1;
while (left < right) {
int mid = (left + right) >> 1;
if (nums[0] <= nums[mid]) {
if (nums[0] <= target && target <= nums[mid]) {
right = mid;
} else {
left = mid + 1;
}
} else {
if (nums[mid] < target && target <= nums[n - 1]) {
left = mid + 1;
} else {
right = mid;
}
}
}
return nums[left] == target ? left : -1;
}
}Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.
Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.