Search in Rotated Sorted Array
题目
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
分析
1.不管在那个点旋转,数组中总有一半是有序的
2.找到有序的一半,并判断target是否在其中,如果在,则在有序的一半中继续查找,否则在另一半查找
3.画图分析
黑色为数组的值,从图中我们可以看出,当nums[low] < nums[mid]的,low-mid一定是有序的,当nums[low] > nums[mid]时,mid-high一定是有序的
4.分析边界条件,假设我们使用mid=(low + high) // 2,当nums[low]=nums[mid]
1)考虑只有一个数的情况,直接用nums[mid] == target就能判断出结果
2)考虑两个数的情况,比如【1,2】或【4,1】。这种情况我们希望我们的算法能对这两个数都判断一遍,因为我们无法确定他们的大小关系。所以先对low判断,再对high判断。发现可以把这一类归类到nums[low] < nums[mid]的情况。
代码:
class Solution:
def search(self, nums: List[int], target: int) -> int:
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
if nums[mid] >= nums[lo]: # lo-mid is ordered
if nums[lo] <= target <= nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else: # mid-hi is ordered
if nums[mid] <= target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1