LeetCode 33

33. 搜索旋转排序数组

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 O(log n) 级别。

示例 1:

输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4

示例 2:

输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1

这道题自己敲完并对照官方的然后发现官方的逻辑比我还复杂，又看到了评论区某位大神的思路，简直绝了，感觉好厉害，就是看了不太懂.... 所以等会在下面会贴出来他的思路和源码，以便之后加强理解
首先是我自己的思路：
老样子还是先找关键词：
①旋转数组：通过看题目相信可以理解他的概念，那么如果想用二分查找找到元素就得分情况讨论了，因为二分的前提是数组顺序排好。所以我们必须找到这个旋转单元，然后通过比较target和旋转单元的大小来在被旋转单元区分的两个区间进行二分查找。
②题目要求时间复杂度log(n) 所以就不能用传统的暴力解法 必须用二分查找。

我的解法其实还可以优化，但今天脑细胞耗费的可以，所以在整体回顾的时候在进行特殊情况的优化。
那么分为两种情况 当数组中元素小于等于2时无法使用二分法，直接遍判断即可。
当数组中的元素大于2时，首先通过for循环遍历找到旋转点，然后判断旋转点和target值，根据情况的不同递归的使用二分查找函数
如果没有旋转点，就说明原数组是正序升序排列，那么直接使用二分查找即可。
下面说说二分查找函数
当数组长度为3时 可能会遇到初始位置与最终位置相等的情况，所以首先得对这个特殊情况进行判断。
然后从起始位置到终止位置（每次都由上一次二分后传入）进行遍历比较，如果找到相等的元素返回即可。
如果没有找到，再对target值和目前长度数组的中间值进行比较，根据比较的大小继续进行二分查找即可。

源代码如下:

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int size = nums.size();
        if (size == 0) {
            return -1;
        }
        if (size <= 2) {
            return findNum(nums, 0, size-1, target);
        }
        int j = 0;
        for (int i = 0; i < size-1; i++) {
            j = i+1;
                if (nums[i] > nums[j]) {
                    if (target >= nums[0]) {
                        return findNum(nums, 0, i, target);
                    } else {
                        return findNum(nums, i+1, size-1, target);
                    }
                }
        }
        //如果没有 说明就是正序
        if (target > nums[size/2]) {
            return findNum(nums, size/2+1, size-1, target);
        } else {
            return findNum(nums, 0, size/2, target);
        }
    }
    
    int findNum(vector<int>& nums, int qPos, int zPos, int target) {
        if (qPos == zPos) {
            if (nums[qPos] == target) {
                return qPos;
            }
            return -1;
        }
        int i = 0;
        for (i = qPos; i <= zPos; i++) {
            if (nums[i] == target) {
                return i;
            } 
        }
        if (target > nums[(qPos+zPos)/2]) {
            return findNum(nums, (qPos+zPos)/2+1, zPos, target);
        } else {
            return findNum(nums, qPos, (qPos+zPos)/2, target);
        }
    }
};

好了，现在说说大神的思路:
简要来说：

nums[0] <= nums[mid]（0 - mid不包含旋转）且nums[0] <= target <= nums[mid] 时 high 向前规约；

nums[mid] < nums[0]（0 - mid包含旋转），target <= nums[mid] < nums[0] 时向前规约（target 在旋转位置到 mid 之间）

nums[mid] < nums[0]，nums[mid] < nums[0] <= target 时向前规约（target 在 0 到旋转位置之间）

其他情况向后规约

也就是说nums[mid] < nums[0]，nums[0] > target，target > nums[mid] 三项均为真或者只有一项为真时向后规约。

原文的分析是：

注意到原数组为有限制的有序数组（除了在某个点会突然下降外均为升序数组）

if nums[0] <= nums[I] 那么 nums[0] 到 nums[i] 为有序数组,那么当 nums[0] <= target <= nums[i] 时我们应该在 0−i0-i0−i 范围内查找；

if nums[i] < nums[0] 那么在 0−i0-i0−i 区间的某个点处发生了下降（旋转），那么 I+1I+1I+1 到最后一个数字的区间为有序数组，并且所有的数字都是小于 nums[0] 且大于 nums[i]，当target不属于 nums[0] 到 nums[i] 时（target <= nums[i] < nums[0] or nums[i] < nums[0] <= target），我们应该在 0−i0-i0−i 区间内查找。
上述三种情况可以总结如下：

nums[0] <= target <= nums[i]
           target <= nums[i] < nums[0]
                     nums[i] < nums[0] <= target

所以我们进行三项判断：

(nums[0] <= target)， (target <= nums[i]) ，(nums[i] < nums[0])，现在我们想知道这三项中有哪两项为真（明显这三项不可能均为真或均为假（因为这三项可能已经包含了所有情况））

所以我们现在只需要区别出这三项中有两项为真还是只有一项为真。

使用 “异或” 操作可以轻松的得到上述结果（两项为真时异或结果为假，一项为真时异或结果为真，可以画真值表进行验证）

之后我们通过二分查找不断做小 target 可能位于的区间直到 low==high，此时如果 nums[low]==target 则找到了，如果不等则说明该数组里没有此项。

只能说牛逼！！！
源代码如下:

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int lo = 0, hi = nums.size() - 1;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if ((nums[0] > target) ^ (nums[0] > nums[mid]) ^ (target > nums[mid]))
                lo = mid + 1;
            else
                hi = mid;
        }
        return lo == hi && nums[lo] == target ? lo : -1;
    }
};