33. Search in Rotated Sorted Array.md

33. Search in Rotated Sorted Array

思路

题意就是在一个经过了循环移位的有序数组（无重复元素）里进行查找，要求时间复杂度O(logn)。
由于要求的时间复杂度为O(logn)，所以肯定是考虑二分查找的。假如这个数组没有进行循环移位，即就是一个有序的，那对其进行查找就是一个简单的二分查找，so easy，时间复杂度O(logn)。怎样把二分查找运用在本题呢?（本文默认你掌握了二分查找，否则建议先去看看二分查找）

思路一

前面也说了，本题的数组就是一个有序数组再经过了循环移位，如下例就是向右循环移位了4步（或者左循环移位了3步）:

     下标:0 1 2 3 4 5 6
移位前元素:0 1 2 4 5 6 7
移位后元素:4 5 6 7 0 1 2

可以看到移位后的元素的下标相当于是移位前的下标加4(然后对7取模)，既然这样，那我们在二分查找判断target和nums[mid]大小之前也对mid加4(然后对7取模)不就行了。(具体实现可参考代码)

现在问题来了，怎样计算这个偏移量4？我们只需要知道一个元素在循环移位前和循环移位后的下标就行了，为了简单不妨去找最小的那个元素，这样其对应的移位后的下标就是偏移量。

由于要求时间复杂度O(logn)，所以应该用二分查找这个最小值。二分查找的时候我们会知道nums[low]、nums[mid]、nums[high]，怎样通过这三个数的大小关系确定最小值在[low, mid]或者[mid, high]哪一个区间呢?

先看来看看nums[low]和nums[mid]比较:

假设nums[low] < nums[mid]，此时最小值可能就是nums[low]比如012或者在[mid, high]区间比如120。

所以拿nums[low]和nums[mid]比较不是一个好选择。再来看看nums[mid]和nums[high]比较:

• 若nums[mid] < nums[high]，此时最小值只能是位于[low, mid]。
• 否则若nums[mid] > nums[high]，此时最小值只能是位于[mid+1, high]。
• 假设nums[mid] == nums[high]，此时low = mid = high，最小值就是nums[mid]。

可见用nums[mid]和nums[high]的大小关系可以确定最小值位于哪一个区间。
知道了最小值，那也就知道了偏移量，再用二分法，问题迎刃而解。

时间复杂度O(logn)，空间复杂度O(1)

思路二

思路一虽然时间复杂度为O(logn)，但是却进行了两次查找，一点都不elegant，能不能直接一步到位呢？肯定还是二分法，那么我们应该如何判断target是在左半部分[low, mid)还是右半部分(mid, high]呢?

我们知道，判断一个数是否在一个有序数组数组是很方便的(只需要判断端点和这个数的大小关系)，幸运的是，仔细分析此题的数组可知，左右两半至少有一半是有序的。所以我们可以判断target是否在这有序的一半，若在则丢弃掉另一半进入下一次循环，若不在则丢弃掉有序的这一半进入下一次循环。那么如何判断哪一半是有序的呢?也很简单，只需要判断左右端点即可，以左半部分为例：

• 若nums[low] <= nums[mid]，则左半部分一定是有序的(想想为什么)；
• 否则左半部分是无序的，则右半部分一定是有序的。

时间复杂度O(logn), 空间复杂度O(1)

注意此题不存在重复值，而81. Search in Rotated Sorted Array II则可能有重复值。81题也是采用思路二，即先判断哪一半是有序的，但是当nums[low] = nums[mid]时无法判断哪一半有序，怎么办呢？很简单，那我们直接low++即可，即退化成顺序查找，所以81题最坏时间复杂度是O(n)，此时数组中元素全相等且不等于target。

C++

思路一

class Solution {
public:
    int search(vector<int>& nums, int target) {
        if(nums.empty()) return -1;
        int len = nums.size();
        int delta, mid, low = 0, high = len - 1; // delta偏移量
        
        // 计算偏移量
        while(low != high){
            mid = low + (high - low) / 2; // 不写成 (low + high) / 2 是为了避免溢出的风险
            if(nums[mid] < nums[high]) high = mid;
            else low = mid + 1; // 注意这里是 mid+1 ！！！
        } // low == high == mid == 偏移量
        delta = low;
        
        // 考虑偏移的二分查找
        low = 0;
        high = len - 1;
        int real_mid;  // 算上偏移的mid
        while(low <= high){
            mid = low + (high - low) / 2;
            real_mid = (mid + delta) % len;   
            if(nums[real_mid] == target) return real_mid;
            else if(nums[real_mid] < target) low = mid + 1;
            else high = mid - 1;
        }
        return -1;
    }
};

思路二

class Solution {
public:
    int search(vector<int>& nums, int target) {
        if(nums.empty()) return -1;
        int len = nums.size();
        int mid, low = 0, high = len - 1;
        while(low <= high){
            mid = low + (high - low) / 2;
            if(nums[mid] == target) return mid;
            if(nums[low] <= nums[mid]){  // 左半边有序
                if(nums[low] <= target && target < nums[mid]) high = mid - 1; // target在左半边
                else low = mid + 1;
            }
            else{  // 右半边有序
                if(nums[mid] < target && target <= nums[high]) low = mid + 1; // target在右半边
                else high = mid - 1;
            }
        }
        
        return -1;
    }
};