Find a Value in an Array Rotated at an Unknown Pivot
Solve this Problem[0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]. Given the rotated array nums and an integer target, return its index, or -1 if it isn't present.
You must solve it in O(log n) time. At every step, at least one of the two halves around mid is guaranteed to be sorted — use that half to decide which side to search next.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ nums.length ≤ 5000 - ◆
-10⁴ ≤ nums[i] ≤ 10⁴ - ◆
Every value in nums is unique - ◆
nums was sorted in ascending order, then rotated at some unknown pivot - ◆
-10⁴ ≤ target ≤ 10⁴
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
| 1 | class Solution { |
| 2 | public int searchRotated(int[] nums, int target) { |
| 3 | int lo = 0, hi = nums.length - 1; |
| 4 | while (lo <= hi) { |
| 5 | int mid = lo + (hi - lo) / 2; |
| 6 | if (nums[mid] == target) return mid; |
| 7 | if (nums[lo] <= nums[mid]) { |
| 8 | if (nums[lo] <= target && target < nums[mid]) { |
| 9 | hi = mid - 1; |
| 10 | } else { |
| 11 | lo = mid + 1; |
| 12 | } |
| 13 | } else { |
| 14 | if (nums[mid] < target && target <= nums[hi]) { |
| 15 | lo = mid + 1; |
| 16 | } else { |
| 17 | hi = mid - 1; |
| 18 | } |
| 19 | } |
| 20 | } |
| 21 | return -1; |
| 22 | } |
| 23 | } |
| 24 |
06Search the rotated array over the full range [0, 6] for target 0.
Approach & Solutions
Brute Force — Linear Scan
BruteRotation doesn't matter if you just check every element one at a time — walk the array and compare each value against target. It works on any array, rotated or not, but it ignores the fact that each half of a rotated sorted array is still individually sorted, which is what lets binary search skip most of the array.
O(n)O(1)1class Solution {
2 public int searchRotated(int[] nums, int target) {
3 for (int i = 0; i < nums.length; i++) {
4 if (nums[i] == target) return i;
5 }
6 return -1;
7 }
8}Optimal — Modified Binary Search
OptimalA rotated sorted array still has a useful property: for any mid, at least one of the two halves [lo, mid] or [mid, hi] is fully sorted. Figure out which half is sorted by comparing nums[lo] to nums[mid]. If target falls inside that sorted half's range, search there; otherwise it must be in the other (still rotated) half — recurse into that one instead.
O(log n)O(1)1class Solution {
2 public int searchRotated(int[] nums, int target) {
3 int lo = 0, hi = nums.length - 1;
4 while (lo <= hi) {
5 int mid = lo + (hi - lo) / 2;
6 if (nums[mid] == target) return mid;
7 if (nums[lo] <= nums[mid]) {
8 if (nums[lo] <= target && target < nums[mid]) {
9 hi = mid - 1;
10 } else {
11 lo = mid + 1;
12 }
13 } else {
14 if (nums[mid] < target && target <= nums[hi]) {
15 lo = mid + 1;
16 } else {
17 hi = mid - 1;
18 }
19 }
20 }
21 return -1;
22 }
23}