Leetcode-33Search in Rotated Sor

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 中的对应位置的基础之上增加一些条件；

对于旋转数组，可能存在两种情况：

1. 旋转数组在左半段；
2. 旋转数组在右半段；

在目标数 target < nums[mid] 的前提下：

1. 如果旋转数组在左半段：
   数组最小值一定在旋转数组中；
   所以数组为：(...数组最小值...) nums[mid] (有序数组，递增)；
   所以目标值只可能在左半段；
2. 如果旋转数组在右半段：
   数组最小值一定在旋转数组中；
   所以数组为：(有序数组，递增) nums[mid] (...数组最小值...)；
   发现目标值不确定在哪半段中；但是我们可以观察到，左半段为递增有序数组，那么只要有序数组中的最小值 nums[begin] > target 的话，目标值就一定在左半段！否则在右半段；
   综上，我们得出：
   在目标数 target < nums[mid] 的前提下：
   如果数组最小值在右半段(旋转数组在右侧) 且 左半段最小值比目标值大；
   取右半段：begin = mid + 1；
   否则取左半段：end = mid - 1；

在目标数 target > nums[mid] 的前提下：

1. 如果旋转数组在左半段：
   数组最大值一定在旋转数组中；
   所以数组为：(...数组最大值...) nums[mid] (有序数组，递增)；
   发现目标值不确定在哪半段中；但是我们可以观察到，右半段为递增有序数组，那么只要有序数组中的最大值 nums[end] < target 的话，目标值就一定在左半段！否则在右半段；
2. 如果旋转数组在右半段：
   数组最小值一定在旋转数组中；
   所以数组为：(有序数组，递增) 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