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<nums[mid]，则在前半部分找，否则去后半部分找。
第三类 6 7 1 2 3 4 5这种，也就是 nums[start] > nums[mid]。此例子中就是 6 > 2； 这种情况下，后半部分有序。因此如果 nums[mid] <target<=nums[end]。则在后半部分找，否则去前半部分找。

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;}
};