33. Search in Rotated Sorted Array
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.
题解：
一个无重复元素的数组和一个目标数 target；将数组以某个下标旋转得到旋转数组 nums，求 target 在旋转数组 nums 中的位置，如果 target 不在 nums 中，返回 -1；
有序数组优先考虑二分查找：https://www.jianshu.com/p/5ca633157c0f
查找 target 在无重复 nums 中的对应位置：https://www.jianshu.com/p/37ae38bdd3a5
我们要求 target 在无重复旋转 nums 中的对应位置，所以要在查找 target 在无重复 nums 中的对应位置的基础之上增加一些条件；
对于旋转数组，可能存在两种情况：
- 旋转数组在左半段；
- 旋转数组在右半段；
在目标数 target < nums[mid] 的前提下：
- 如果旋转数组在左半段：
数组最小值一定在旋转数组中；
所以数组为：(...数组最小值...) nums[mid] (有序数组，递增)；
所以目标值只可能在左半段； - 如果旋转数组在右半段：
数组最小值一定在旋转数组中；
所以数组为：(有序数组，递增) nums[mid] (...数组最小值...)；
发现目标值不确定在哪半段中；但是我们可以观察到，左半段为递增有序数组，那么只要有序数组中的最小值 nums[begin] > target 的话，目标值就一定在左半段！否则在右半段；
综上，我们得出：
在目标数 target < nums[mid] 的前提下：
如果数组最小值在右半段(旋转数组在右侧) 且 左半段最小值比目标值大；
取右半段：begin = mid + 1；
否则取左半段：end = mid - 1；
在目标数 target > nums[mid] 的前提下：
- 如果旋转数组在左半段：
数组最大值一定在旋转数组中；
所以数组为：(...数组最大值...) nums[mid] (有序数组，递增)；
发现目标值不确定在哪半段中；但是我们可以观察到，右半段为递增有序数组，那么只要有序数组中的最大值 nums[end] < target 的话，目标值就一定在左半段！否则在右半段； - 如果旋转数组在右半段：
数组最小值一定在旋转数组中；
所以数组为：(有序数组，递增) nums[mid] (...数组最大值...)；
所以目标值只可能在右半段；
综上，我们得出：
在目标数 target > nums[mid] 的前提下：
如果数组最大值在左半段(旋转数组在左侧) 且 右半段最大值比目标值小；
取左半段：end = mid - 1；
否则取右半段：begin = mid + 1；
My Solution(C/C++)
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
int search(vector<int> &nums, int target) {
int begin = 0;
int end = nums.size() - 1;
while (begin <= end) {
int mid = (begin + end) / 2;
if (target == nums[mid]) {
return mid;
}
else if (target < nums[mid]) {
if (nums[mid] > nums[end] && nums[begin] > target) { //数组最小值在右半段(旋转部分在右侧) && 左半段最小值比目标值大
begin = mid + 1; //在右半段查找目标值
}
else {
end = mid - 1; //在左半段查找目标值
}
}
else if (target > nums[mid]) {
if (nums[begin] > nums[mid] && target > nums[end]) { //数组最大值在左半段(旋转部分在左侧) && 右半段最大值比目标值小
end = mid - 1; //在左半段查找目标值
}
else {
begin = mid + 1; //在右半段查找目标值
}
}
}
return -1;
}
};
int main() {
vector<int> nums;
nums.push_back(4);
nums.push_back(5);
nums.push_back(6);
nums.push_back(7);
nums.push_back(0);
nums.push_back(1);
nums.push_back(2);
Solution s;
printf("%d ", s.search(nums, 0));
return 0;
}
结果：
4
My Solution(Python)
class Solution:
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
result = self.search_rotated_array(0, len(nums) - 1, nums, target)
return result
def search_rotated_array(self, begin, end, nums, target):
while begin <= end:
mid = (begin + end) // 2
if nums[begin] <= nums[mid]: #右侧为旋转数组
if nums[mid] == target:
return mid
elif nums[mid] > target:
if nums[begin] > target: #目标数只可能在右侧旋转数组中
begin = mid + 1
self.search_rotated_array(begin, end, nums, target) #递归，将右侧旋转数组划分为排序数组和旋转数组继续查找
else: #目标数只可能在左侧排序数组中
end = mid - 1
else: #目标数不在左侧排序数组中
begin = mid + 1
self.search_rotated_array(begin, end, nums, target) #递归，将右侧旋转数组划分为排序数组和旋转数组继续查找
else: #左侧为旋转数组
if nums[mid] == target:
return mid
elif nums[mid] > target: #目标数只可能在左侧旋转数组中
end = mid - 1
self.search_rotated_array(begin, end, nums, target) #递归，将左侧旋转数组划分为排序数组和旋转数组继续查找
else:
if nums[-1] < target: #目标数只可能在左侧旋转数组中
end = mid - 1
self.search_rotated_array(begin, end, nums, target) #递归，将左侧旋转数组划分为排序数组和旋转数组继续查找
else: #目标数只可能在右侧排序数组中
begin = mid + 1
return -1
ps:蠢哭了
My Solution2.0:
class Solution:
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
begin, end = 0, len(nums) - 1
while begin <= end:
mid = (begin + end) // 2
if nums[begin] <= nums[mid]: #右侧为旋转数组
if nums[mid] == target:
return mid
elif nums[mid] > target:
if nums[begin] > target: #目标数只可能在右侧旋转数组中
begin = mid + 1
else: #目标数只可能在左侧排序数组中
end = mid - 1
else: #目标数不在左侧排序数组中
begin = mid + 1
else: #左侧为旋转数组
if nums[mid] == target:
return mid
elif nums[mid] > target: #目标数只可能在左侧旋转数组中
end = mid - 1
else:
if nums[-1] < target: #目标数只可能在左侧旋转数组中
end = mid - 1
else: #目标数只可能在右侧排序数组中
begin = mid + 1
return -1
