搜索旋转排序数组
33. 搜索旋转排序数组
难度中等651收藏分享切换为英文关注反馈
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [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
答：
def search(nums, target):
left,right=0,len(nums)-1
while left<=right:
mid=(left+right)//2
if target==nums[mid]:
return mid
#左侧区间 [left,mid]「连续递增」
if nums[0]<=nums[mid]:
if nums[0]<=target<nums[mid]:
right=mid-1
else:
left=mid+1
#右侧区间 [mid,right]「连续递增」
else:
if nums[mid]<target<=nums[len(nums)-1]:
left=mid+1
else:
right=mid-1
return -1
解析做法：
看到复杂度为O(logn),应该是二分查找，二分查找的过程就是不断收缩左右边界，这道题就是在二分查找的基础上改进，增加判断连续区域部分
- 普通二分法：
若 target == nums[mid]，直接返回
若 target < nums[mid]，则 target 位于左侧区间 [left,mid) 中。令 right = mid-1，在左侧区间查找
若 target > nums[mid]，则 target 位于右侧区间 (mid,right] 中。令 left = mid+1，在右侧区间查找
- 根据旋转数组的特性，当元素不重复时，如果 nums[i] <= nums[j]，说明区间 [i,j] 是「连续递增」的。
i、j 可以重合，因此，在旋转排序数组中查找一个特定元素时：
若 target == nums[mid]，直接返回
若 nums[left] <= nums[mid]，说明左侧区间 [left,mid]「连续递增」。此时：
若 nums[left] <= target <= nums[mid]，说明 target 位于左侧。令 right = mid-1，在左侧区间查找
否则，令 left = mid+1，在右侧区间查找
否则，说明右侧区间 [mid,right]「连续递增」。此时：
若 nums[mid] <= target <= nums[right]，说明 target 位于右侧区间。令 left = mid+1，在右侧区间查找
否则，令 right = mid-1，在左侧区间查找
与nums[0]比较判断是都连续，哪部分连续