Description

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


Solutions

分清楚什么时候向前，什么时候向后规约即可。值得注意的是：

1. 如果 mid 对应的数小于最右边的数的话，那么右侧就是有序的，则就着右边的进行判断，如果 target 在右侧之间，那么更新 l 指针，否则就更新 r 指针
2. 如果 mid 对应的数大于最右边的数的话，那么左侧是有序的，如上调整两个指针
# Time: O(n)
# Space: O(1)
class Solution:
def search(self, nums: List[int], target: int) -> int:
if not nums or len(nums) == 0:
return -1
n = len(nums)
l, r = 0, n-1
while l <= r:
mid = (l + r) >> 1
if nums[mid] == target:
return mid
elif nums[mid] < nums[r]:
if nums[mid] < target <= nums[r]:
l = mid + 1
else:
r = mid - 1
else:
if nums[l] <= target < nums[mid]:
r = mid - 1
else:
l = mid + 1
return -1
# 196/196 cases passed (44 ms)
# Your runtime beats 83.98 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.8 MB)


看到更快的解法，把等于号给独立出来了，其实一样，但是能减少一些计算：

class Solution:
def search(self, nums: List[int], target: int) -> int:
low, high = 0, len(nums)-1

while low <= high:
mid = low + (high - low)//2
if nums[mid] == target:
return mid
if nums[low] == target:
return low
if nums[high] == target:
return high
elif nums[mid] < nums[high]:
if nums[mid] < target and target < nums[high]:
low = mid + 1
else:
high = mid - 1
else:
if nums[low] < target and target < nums[mid]:
high = mid - 1
else:
low = mid + 1

return -1