05 August 2008
Suppose an array sorted in ascending order 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.
Your algorithm’s runtime complexity must be in the order of O(log n).
Example 1:
1
2
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:
1
2
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
一个已经升序排好的数组以某个轴rotated调转左右的元素，然后在调转后的array里寻找到指定的元素，找到就返回index，没找到则返回-1，数组里的元素是没有重复的。
这道题是上一道题35 - Search Insert Position的变体，看似有点麻烦，其实理清一下还是比较简单的。 因为rotate的缘故，当切取一半的时候要做进一步的判断。具体来说，假设数组是nums，每次左边缘为left，右边缘为right，还有中间位置是 mid。在每次迭代中，分三种情况：
（1）如果nums[mid] == target，那么mid就是我们要的结果，直接返回；
（2）如果nums[mid] < nums[right]，那么说明从mid到right一定是有序的（没有受到rotate的影响），那么这时候判断target是不是在mid到right之间，如果是则把左边缘移到mid+1，如果不是就右边缘移到mid-1。
（3）如果nums[mid] >= nums[right]，那么说明mid到right收到了rotate的影响，而从left到mid一定是有序的，这时候同样判断target在哪个范围，然后相应的移动边缘即可。
所以先根据nums[mid]的值跟nums[left]或者nums[right]比较，可以先知道mid左右两边哪边是有序的，然后再先判断target是否在有序的部分，so on and so forth，每次都可以去掉一半的数据，Time是O(logn)，Space是O(1)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public int search(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return -1;
}
int left = 0, right = nums.length - 1;
// 利用模板，1. 先跟right比较，判断有序的是左侧还是右侧，2. 再“先”在其中判断target是否在有序的该侧
while (left + 1 < right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} if (nums[mid] > nums[right]) { // 左侧有序
if (nums[left] == target) {
return left;
} else if (nums[left] < target && nums[mid] > target) { // 哪边有序则double check target是否在有序的这一侧
right = mid;
} else { // 在乱序的右侧
left = mid;
}
} else { // 右侧有序
if (nums[right] == target) {
return right;
} else if (nums[right] > target && nums[mid] < target) {// 哪边有序则double check target是否在有序的这一侧
left = mid;
} else { // 在乱序的左侧
right = mid;
}
}
}
if (nums[left] == target) { // post-processing
return left;
} else if (nums[right] == target) {
return right;
}
return -1;
}
}
没那么多if statements
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public int search(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return -1;
}
int left = 0;
int right = nums.length - 1;
while (left + 1 < right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] > nums[right]) { //左侧有序
if (nums[left] <= target && nums[mid] > target) { // 判定target是否在有序的左侧
right = mid;
} else { // 在乱序的右侧
left = mid;
}
} else { // nums[mid] < nums[right]，右侧有序
if (nums[right] >= target && nums[mid] < target) { // 判定target是否在有序的右侧
left = mid;
} else {// 在乱序的左侧
right = mid;
}
}
}
if (nums[left] == target) {
return left;
}
return nums[right] == target ? right : -1;
}
}