33. Search in Rotated Sorted Array

寻找旋转排序数组

There is an integer array nums sorted in ascending order (with distinct values).
一个升序排序的整数数组
Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].
按照其中某个未知的下标k为轴进行旋转，即将这个下标之后的列表排序到前面。
Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.
给定一个旋转过后的nums列表，和一个数字。判断数字是否存在列表中。

You must write an algorithm with O(log n) runtime complexity.
看到时间复杂度O(log n)就会想到二分查找。

Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Example 3:
Input: nums = [1], target = 0
Output: -1

Constraints:
1 <= nums.length <= 5000
-104 <= nums[i] <= 104
All values of nums are unique.
nums is an ascending array that is possibly rotated.
-104 <= target <= 104

思考

从题目提及的时间复杂度，可以知道这次肯定是需要用到二分法的。
我们先分析一下旋转之后(r1,r2)->(r2,r1)的列表。 [4,5,6,7,0,1,2] 这样一个列表，我们可以知道，因为是将升序列表的r2部分移植到了r1部分，所以移植之后前半部分的每一个值是肯定比后半部分的每一个值大的。但是可能存在旋转轴位两端端点的情况，这样的话就不排除会存在数组依旧排序正常的情况。
这时候如果我们二分法。就要分情况来讨论。

1、二分的时候分在前半部分
即分完之后的left部分的正常升序，right部分乱序。
如果target存在于left部分就正常二分查找进行查找，如果存在right还得继续分，并继续讨论（这里的话就有点递归的感觉在里面了）
2、二分的时候分在后半部分
和第一种情况一样，分情况讨论。
3、正常顺序
即旋转之后仍然是正常顺序，直接二分法查找。

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not bool(nums):
            return -1
        
        l_n = len(nums)
        sp = int(l_n/2)
        ret = -1
        
        if l_n == 1:
            if nums[0]==target:
                return 0
            else:
                return -1
        
        if nums[-1]>nums[0]:
            if target>=nums[0] and target<=nums[-1]:
                if nums[sp]>target:
                    ret = self.search(nums[:sp], target)
                else:
                    tmp = self.search(nums[sp:], target)
                    if tmp!=-1:
                        tmp+=sp
                    ret = tmp
            else:
                return -1
        else:
            tmp1 = self.search(nums[:sp], target)
            tmp2 = self.search(nums[sp:], target)
            if tmp2!=-1:
                tmp2+=sp
                
            ret = max(tmp1, tmp2)
        return ret

目测一下，因为使用了二分法所以时间复杂度为O(log n)
空间复杂度并没有用到其他空间，应该就是O(n)

答案解析

二分法

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:
            mid = (l + r) // 2
            if nums[mid] == target:
                return mid
            if nums[0] <= nums[mid]:
                if nums[0] <= target < nums[mid]:
                    r = mid - 1
                else:
                    l = mid + 1
            else:
                if nums[mid] < target <= nums[len(nums) - 1]:
                    l = mid + 1
                else:
                    r = mid - 1
        return -1

答案给的也是二分，但是跑出来的结果表现没我自己写的好，哈哈。
的确，只要二分之后，必然有一个是有序的，另一部分是旋转顺序的。
他通过用nums[0]和nums[mid]来判断左右哪一边是有序的。在知道哪一部分是有序的之后，可以用升序的特性来判断target是否存在有序的这一部分，如果存在则在其中进行搜索，如果不在就在无序的那半部分进行搜索。

总结

能够递归的必然能够迭代
答案来自美国站leetcode和中国站力扣。仅供学习参考