#33 Search in Rotated Sorted Array——Top 100 Liked Questions

今天药忘吃喽~ 2022-02-01 08:13 158阅读 0赞

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., `[0,1,2,4,5,6,7]` might become `[4,5,6,7,0,1,2]`).

You are given a target value to search. If found in the array return its index, otherwise return `-1`.

You may assume no duplicate exists in the array.

Your algorithm's runtime complexity must be in the order of *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

> """
> 
> 第一次：先找到最大值max(nums)及索引，并将其设为mid，left为0，right为len(nums)-1，这样讲nums分成了两部分，然后通过判断target与nums\[left\]与nums\[right\]的大小，判断target在左半部分还是右半部分，然后再对左右两部分应用二叉搜索；复杂度我不会计算，应该是不满足O（log n）的
> 
> """
> 
> class Solution(object):  
>     def search(self, nums, target):  
>         """  
>         :type nums: List\[int\]  
>         :type target: int  
>         :rtype: int  
>         """  
>         if len(nums) == 0: return -1  
>         left = 0  
>         right = len(nums) - 1  
>         mid = nums.index(max(nums))    
>         if target == nums\[mid\]:  
>             return mid  
>         elif target >= nums\[left\]:  
>             left = 0  
>             right = mid - 1  
>             while left <= right:  
>                 mid = (left + right) // 2  
>                 if nums\[mid\] == target:  
>                     return mid  
>                 elif nums\[mid\] > target:  
>                     right = mid - 1  
>                 else:  
>                     left = mid + 1  
>         elif target <= nums\[right\]:  
>             left = mid + 1  
>             right = len(nums) - 1  
>             while left <= right:  
>                 mid = (left + right) // 2  
>                 if nums\[mid\] == target:  
>                     return mid  
>                 elif nums\[mid\] > target:  
>                     right = mid - 1  
>                 else:  
>                     left = mid + 1  
>         return -1
> 
> """
> 
> Runtime: 24 ms, faster than 66.13% of Python online submissions for Search in Rotated Sorted Array.
> 
> Memory Usage: 12.1 MB, less than 5.44% of Python online submissions for Search in Rotated Sorted Array.
> 
> """