33.SearchRotatedSortedArray题目来源：https://leetcode-cn.com/problems/search-in-rotated-sorted-array/题目假设一个数组按升序排序旋转是在事先未知的某个点进行的。（例如，数组[0,1,2,4,5,6,7]可能变为[4,5,6,7,0,1,2]）。搜索给定的目标值，如果它存在于数组中则返回其索引，否则返回-1。您可以假设数组中没有重复元素。你的算法时间复杂度必须是O(logn)级别。示例1：输入：nums=[4,5,6,7,0,1,2]，target=0输出：4示例2：输入：nums=[4,5,6,7,0,1,2],target=3输出：-1解题思路：在二分查找问题中，算法的时间复杂度必须是O(logn)级别。这里其实是提示可以使用二分查找法。需要注意的一点是，二分查找要求列表的元素必须是有序的。在这里，虽然原始数组是按升序排序的，但在某个未知点旋转数组后，列表只是部分排序。但实际上，这里并不冲突，因为当旋转列表分为两部分时，一部分必须是有序的。直接以例1为例，[4,5,6,7,0,1,2]，如果数组分为[4,5,6]和[7,0,1,2]，则previous[4,5,6]这部分是有顺序的。对于满足这些条件的其他阵列也是如此。上面说了数组被分成了两部分，那么我们可以考虑从中点的位置开始把原数组分成[left,mid]和[mid+1,right]两部分。当旋转数组分为以上两部分时，现在要考虑的是目标值，会落在哪个区间？当目标值落在有序部分的区间内时，这个就比较容易理解了。这时候上下边界就确定了，题目也写着【可以假设数组中没有重复的元素。]，则只有一个元素与之匹配。现在具体分析判断目标会落在哪个区间：如果[left,mid-1]部分是有序的，而目标落在区间[nums[left],nums[mid])，那么搜索到的范围缩小到[left,mid-1]，否则会在区间[mid+1,right]进行搜索；如果[mid,right]部分是有序的，并且目标落在(nums[mid+1],nums[right]]，则在区间[mid+1,right]中搜索，否则在区间[left]中搜索,mid-1].下面是具体的代码实现。代码实现类解决方案：defsearch(self,nums:List[int],target:int)->int:#当nums为空时，直接返回-1ifnotnums:return-1#初始左右边界left,right=0,len(nums)-1#判断区间的哪一部分是有序的#判断目标会落在哪个区间whileleft<=right:#数组分为两部分mid=(left+right)//2#如果target的值等于划分区间的元素时，直接返回ifnums[mid]==target:returnmid#判断区间是否有序#这里表示[left,mid-1]是有序的ifnums[0]<=nums[mid]:#target落在区间[left,mid-1]ifnums[0]<=target
