【LeetCode】33.搜索旋转排序数组
1. 题目
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