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.

 

先用二分法找到pivot。判断target应该是在前一段还是后一段。然后在相应的那一段做二分法搜索。注意L39, 如果l - r ==1 这说明r就是pivot了，不能一直搜到 l == r.

1 class Solution(object): 2     def search(self, nums, target): 3         """ 4         :type nums: List[int] 5         :type target: int 6         :rtype: int 7         """ 8         pivot = self.findP(nums) 9         if nums[pivot] <= target <= nums[-1]:10             ans = self.BS(nums[pivot:], target)11             if ans != -1:12                 return ans + pivot13             else:14                 return -115         elif nums[0] <= target <= nums[pivot-1]:16             return self.BS(nums[:pivot], target)17         else:18             return -119     20     21     def BS(self, nums, target):22         n = len(nums)23         l, r = 0, n-124         while l <= r:25             mid = (l + r)//226             if nums[mid] == target:27                 return mid28             elif nums[mid] < target:29                 l = mid + 130             else:31                 r = mid - 132         return -133         34     def findP(self, nums):35         n = len(nums)36         if nums[0] <= nums[n-1]:37             return 038         l, r = 0, n -139         while l < r and r - l > 1:40             mid = (l+r)//241             if nums[l] > nums[mid]:42                 r = mid 43             elif nums[mid] > nums[r]:44                 l = mid 45         return r 46