https://leetcode-cn.com/problems/search-in-rotated-sorted-array/
整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
我的方法一：先找到旋转点，然后再确定是在哪一段来二分查找
步骤：
- 判断是否有旋转，即判断第一位是否大于最后一位
- 当有旋转时，寻找旋转点
2.1 begin和end分别表示数组的第一位和最后一位
2.2 取中间点middle，判断middle是否比middle+1位数要大
2.2.1 如果大，那么middle就是旋转点
2.2.2 如果不大，当middle值比第一位小，那么end=middle-1
2.2.3 如果不大，当middle值比第一位大，那么begin=middle+1 - 确定target在哪一段，即求的begin和end
初始值
- begin=0， end=nums.size()-1
边界条件
- begin要<=end
- nums的长度是否0或者1
复杂度
时间复杂度：O(logn)，寻找旋转点和寻找target都采用二分查找
空间复杂度：O(1)，只使用来begin、end、middle几个变量
代码
出现一个错误，就是当找到旋转点时一定要break；
class Solution {
public:
int search(vector<int>& nums, int target) {
if(nums.size()==0){
return -1;
}else if(nums.size()==1){
return nums[0]==target?0:-1;
}
int begin = 0;
int end = nums.size()-1;
int middle = 0;
//1. 判断是否有旋转，即判断第一位是否大于最后一位
if(nums[begin] > nums[end]){
while(begin <= end){
//2.2 取中间点middle，判断middle是否比middle+1位数要大
middle=(begin+end)>>1;
if(nums[middle] > nums[middle+1]){
//2.2.1 如果大，那么middle就是旋转点
if(nums[middle] == target){
return middle;
}else if(nums[middle] < target){
return -1;
}else{
if(target >= nums[0] && target<= nums[middle]){
begin = 0;
end = middle;
}else if(target >= nums[middle+1] && target<= nums[nums.size()-1]){
begin = middle+1;
end = nums.size()-1;
}else{
return -1;
}
}
break;
}else{
if(nums[middle] < nums[0]){
//2.2.2 如果不大，当middle值比第一位小，那么end=middle-1
end = middle-1;
}else{
//2.2.3 如果不大，当middle值比第一位大，那么begin=middle+1
begin = middle+1;
}
}
}
}
//cout<<"begin:"<<begin<<" end:"<<end<<endl;
//3. 确定target在哪一段，即求的begin和end
while(begin <= end){
middle = (begin+end)>>1;
if(nums[middle] == target){
return middle;
}else if(nums[middle] < target){
begin = middle+1;
}else{
end = middle-1;
}
}
return -1;
}
};
其他人的更好解法
官方解法
https://leetcode-cn.com/problems/search-in-rotated-sorted-array/solution/sou-suo-xuan-zhuan-pai-xu-shu-zu-by-leetcode-solut/
不需要寻找旋转点，直接在原数组上二分查找，思路更加清晰
步骤
- begin和end分别指向要搜索的一段区间
- 判断middle
2.1 如果nums[begin] <= nums[middle]，说[begin, middle]是有序的数组
2.1.1 target==nums[begin], target是begin
2.1.2 target==nums[middle], target是middle
2.1.3 target>nums[begin] && nums[middle]> target，那么target肯定在[begin, middle-1]内
2.1.4 否则[middle+1, end]内
2.2 如果nums[begin] > nums[middle]，说[middle,end]是有序的数组
2.1.1 target==nums[end], target是end
2.1.2 target==nums[middle], target是middle
2.1.3 target>nums[middle] && nums[end]> target，那么target肯定在[middle+1, end]内
2.1.4 否则[begin, middle-1]内
代码
class Solution {
public:
int search(vector<int>& nums, int target) {
if(nums.size()==0){
return -1;
}
int begin = 0;
int end = nums.size()-1;
int middle = 0;
while(begin <= end){
middle = (begin+end)>>1;
//cout << "begin:"<<begin<<" end:"<< end<<" mid:"<<middle<<endl;
if(nums[begin] <= nums[middle]){
if(target == nums[begin]){
//2.1.1 target==nums[begin], target是begin
return begin;
}else if(target == nums[middle]){
//2.1.2 target==nums[middle], target是middle
return middle;
}else if(target > nums[begin] && nums[middle]> target){
////2.1.3 target>nums[begin] && nums[middle]> target，那么target肯定在[begin, middle-1]内
end = middle-1;
}else{
//2.1.4 否则[middle+1, end]内
begin = middle+1;
}
}else{
if(target==nums[end]){
//2.1.1 target==nums[end], target是end
return end;
}else if(target==nums[middle]){
//2.1.2 target==nums[middle], target是middle
return middle;
}else if(target>nums[middle] && nums[end]> target){
//2.1.3 target>nums[middle] && nums[end]> target，那么target肯定在[middle+1, end]内
begin = middle+1;
}else {
//2.1.4 否则[begin, middle-1]内
end = middle-1;
}
}
}
return -1;
}
};
