1. leetcode.cn/problems/search-in-rotated-sorted-array/?envType=study-plan-v2&envId=top-interview-150" rel="nofollow">题目
2. 分析
说实话,这道题挺难想的。难点在于,数组非完全有序就会让人产生错觉(这道题无法二分)。如果不是题目要求O(logn)
的复杂度,那我觉得我肯定不会想到。可以这么分析:
对于一个旋转排序数组,其长相如下:
二分切割后,一定满足:至少有一半儿是有序的。基于这个性质,可以得到下面这个代码。
3. 代码
class Solution:def search(self, nums: List[int], target: int) -> int:left = 0right = len(nums) - 1while(left <= right):mid = (left + right) // 2if nums[left] <= nums[mid]: # 左区间完全有序if nums[mid] == target:return midif nums[left] <= target < nums[mid]:right = mid-1else:left = mid+1elif nums[mid] <= nums[right]: # 右区间if nums[mid] == target:return midif nums[mid] < target <= nums[right]:left = mid + 1else:right = mid - 1return -1