Question
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
Stats
| Frequency | 3 |
| Difficulty | 4 |
| Adjusted Difficulty | 4 |
| Time to use | ---------- |
Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)
Analysis
This question is not very difficult, yet commonly seen in interviews.
Without having any knowledge of pivot, we can check the mid-point value against left value and right value. Read this blog for more.
Solution
The code is easy to understand.
My code
Pay special attention to different larger/smaller conditions. It’s very easy to miss a equal sign or something.
public class Solution {
public int search(int[] A, int target) {
if (A == null || A.length == 0) {
return -1;
}
int len = A.length;
int left = 0;
int right = len - 1;
while (left + 1 < right) {
int mid = left + (right - left) / 2;
if (A[mid] == target) {
return mid;
} else if (A[left] < A[mid]) {
// remember to pay attention to (A[left] == target) case
if (A[left] <= target && target < A[mid]) {
right = mid;
} else {
left = mid;
}
} else {
// remember to pay attention to (A[right] == target) case
if (A[mid] < target && target <= A[right]) {
left = mid;
} else {
right = mid;
}
}
}
if (A[left] == target) {
return left;
} else if (A[right] == target) {
return right;
}
return -1;
}
}