33. 搜索旋转排序数组(medium)

假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [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

• show the code:

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        l,r = 0,len(nums)-1
        while l < r:
            m = (l+r)//2
            if nums[l] <= nums[m] and nums[l]<=target<=nums[m]:
                r = m
            elif nums[l] > nums[m] and target>=nums[l]>nums[m]:
                r = m
            elif nums[l] > nums[m] and target<=nums[m]<nums[l]:
                r = m
            else:
                l = m+1
        return l if nums[l]==target else -1

• 此题还比较难，我之前面小米时也被问到过，当时把所有情况都列了出来，其实现在看来是不能AC的。
• 首先题目要求log(n)的复杂度，所以一定是用二分法。其次关键点是要找出所有需要在前半段找的情况，总共只有三种：

1.nums[0] <= nums[mid],（0-mid不包含旋转）且nums[0] <= target <= nums[mid]时high向前规约；
2.nums[mid] < nums[0]（0-mid包含旋转），target <= nums[mid] < nums[0]时向前规约（target在旋转位置到mid之间）
3.nums[mid] < nums[0]，nums[mid] < nums[0] <= target时向前规约（target在0到旋转位置之间）

• 我们只需要考虑比较三个数：第一个数，中间的数和target即可确定我们要不要在前半段找。
• 如果前半段没有旋转，而且目标值在第一个数和中间数之间，那么肯定在前半段。
• 如果前半段有旋转，说明旋转位置在前半段。而目标值在旋转位置到中间数之间，也在前半段中寻找。如果目标值在第一个数到旋转位置之间，则也在前半段中找，也就是说：如果目标值处于(mid,left)区间之外，我们都需要在前半段中寻找。
• 找出在前半段中寻找的所有条件，其他条件就是在后半段中寻找，注意后半段中寻找时，不要包括中间数，不然会陷入死循环—考虑nums=[4,5],target=4，具体表现为l = m+1。
• 由于每次缩小一半的查找范围，时间复杂度可以达到log(n)，空间复杂度为1。