力扣hot100：33. 搜索旋转排序数组（二分的理解）

33.搜索旋转排序数组

这是一个非常有趣的问题，如果不要求使用O(logn)应该没人会想到吧。。

方法一：

极致的分类讨论。旋转排序数组，无非就是右边的增区间的数小于左边的增区间的数，然后依次排序。因此我们只需要分三类讨论即可，即[left,right]在左增区间，[left,right]在右增区间，[left,right]在两个区间中间。只有最后一种情况需要讨论更多一点。

前两种情况可以合并为nums[left]<=nums[right]时的情况，这样一定是有序数组。

最后一种情况又分为，target在左增区间中，target在右增区间中、nums[mid]在左增区间中、nums[mid]在右增区间中：一共4种情况。

如果target在左增区间中，则有target>nums[right]，

如果target在右增区间中，则target<=nums[right]，

如果nums[mid]在左增区间中，则有nums[mid]>nums[rgiht],

如果nums[mid]在右增区间中，则有nums[mid]<=nums[rgiht],

如果使得right=mid-1;则有target在mid左边，则有两种情况：

①mid在右增区间中，target小于mid的值或者 target大于mid的值且大于nums[right]的值，即target在左增区间中。

②mid在左增区间中，target小于mid的值且target也在左增区间中
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left=0,right=nums.size()-1;
        while(left<=right){
            int mid=(left+right)>>1;
            if(nums[mid]==target) return mid;
            if(nums[left]>=nums[0]&&nums[right]>=nums[0]){
                if(nums[mid]>target) {right=mid-1;continue;}
            }else{
                if(nums[left]<nums[0]&&nums[right]<nums[0]){
                    if(nums[mid]>target) {right=mid-1;continue;}
                }else{
                    if(nums[left]>=nums[0]&&nums[right]<nums[0]){
                        if(nums[mid]>nums[right]&&target<nums[mid]&&target>nums[right]){right=mid-1;continue;}
                        if(nums[mid]<=nums[right]&&(target>nums[right]||target<nums[mid])) {right=mid-1;continue;}
                    }
                }
            }
            left=mid+1;
        }
        return -1;
    }
};
/*
或者讨论target在哪个区间
if(target>nums[right]&&(target<nums[mid]||nums[mid]<nums[right])){right=mid-1;continue;}
if(target<nums[right]&&target<nums[mid]&&nums[mid]<=nums[right]) {right=mid-1;continue;}
*/
合并情况：
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left=0,right=nums.size()-1;
        while(left<=right){
            int mid=(left+right)>>1;
            if(nums[mid]==target) return mid;
            if(nums[left]<=nums[right]){
                if(nums[mid]>target) {right=mid-1;continue;}
            }else{
                    if(nums[mid]>nums[right]&&target<nums[mid]&&target>nums[right]) {right=mid-1;continue;}
                    if(nums[mid]<=nums[right]&&(target>nums[right]||target<nums[mid])) {right=mid-1;continue;}
                }
            left=mid+1;
        }
        return -1;
    }
};
方法二：官方思路：

一个区间分为左增区间和右增区间，那么在任意一个点将这个区间断开分为两个区间一定会有一个区间是顺序区间！我们保证每次只在那个顺序区间里找（doge），如果不在这个顺序区间里我们就直接将指针移入那个区间即可，这保证了每一次也是二分的。
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = (int)nums.size();
        if (!n) {
            return -1;
        }
        if (n == 1) {
            return nums[0] == target ? 0 : -1;
        }
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target) return mid;
            if (nums[l] <= nums[mid]) {//左区间是顺序区间
                if (nums[l] <= target && target < nums[mid]) {//target在左区间内则r=mid-1
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else {//右区间是顺序区间
                if (nums[mid] < target && target <= nums[n - 1]) {//target在右区间内则l=mid+1
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        return -1;
    }
};