leetcode每日一题31

搜索旋转排序数组

那……二分法呗
数组中的数可以相同

比 33. 搜索旋转排序数组 多了一个「有重复元素」，导致无法根据 num >= nums[0] 来判断 num 在哪一半，比如
[1,1,1,1,1,2,1,1,1] 旋转数组两头相等，元素 1 可能在左半边可能在右半边
解决方法也很简单，只要把「旋转数组两头相等」这种特殊情况排除掉就行了

排除掉旋转数组两头相等的情况后，再像33一样判断从哪分
因为只旋转了一次，所以数组分为两段，两端分别是排序数组，那么mid一定会落入其中一种排序好的数列里
如果mid比start大，那么前一半是排序数组，如果mid比end小，那么后一半是排序数组
二分法的难点是代码的细节
以下引用自大佬的题解

第一类 1 0 1 1 1这种。此种情况下 nums[start] == nums[mid]，分不清到底是前面有序还是后面有序，此时 start++ 即可。相当于去掉一个重复的干扰项。
第二类 2 3 4 5 6 7 1这种，也就是 nums[start] < nums[mid]。此例子中就是 2 < 5； 这种情况下，前半部分有序。因此如果 nums[start] <=target 第三类 6 7 1 2 3 4 5这种，也就是 nums[start] > nums[mid]。此例子中就是 6 > 2； 这种情况下，后半部分有序。因此如果 nums[mid]

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int start=0;
        int end=nums.size()-1;
        int mid;
        while(start<=end)
        {
            mid=start+(end-start)/2;
            if(nums[mid]==target)
                return true;
            if(nums[start]==nums[mid])
                start++;
            else if(nums[start]<nums[mid])
            {
                if(nums[start]<=target&&nums[mid]>target)
                    end=mid-1;
                else{
                    start=mid+1;
                }
            }
            else{
                if(nums[end]>=target&&nums[mid]<target)
                    start=mid+1;
                else end=mid-1;
            }
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30