题目：

Suppose a sorted array 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

 

代码：oj测试通过 Runtime: 53 ms

1 class Solution: 2     # @param A, a list of integers 3     # @param target, an integer to be searched 4     # @return an integer 5     def search(self, A, target): 6         # none case & zero case 7         if A is None or len(A)==0 : 8             return -1 9         # binary search10         start = 011         end = len(A)-112         while start<=end :13             # one element left case14             if start == end :15                 if A[start]==target :16                     return start17                 else:18                     return -119             # two elements left case20             if start+1 == end :21                 if A[start]==target :22                     return start 23                 elif A[end]==target :24                     return end25                 else:26                     return -127             # equal or more than three elements case28             mid = (start+end)/229             if A[mid]==target :30                 return mid31             elif A[mid]>target:32                 if A[start]>A[mid] and A[end]
     
      =target:36                         start = mid+137                     else:38                         end = mid-139                 elif A[start]>A[mid] and A[end]>A[mid]:40                     end = mid-141                 else:42                     end = mid-143             else:44                 if A[start]>A[mid] and A[end]
      
       A[mid] and A[end]>A[mid]:49                     if A[end]>=target :50                         start = mid+151                     else:52                         end = mid-153                 else:54                     start = mid+155         return -1
      
     

思路：

这个就是binary search的思路。

个人没想出来什么好的方法，硬着头皮硬写了一个暴力解决方法。

传统的binary search只需要判断A[mid]与target的大小就可以了；但这道题是rotated array，光判断A[mid]是不够的。

还需要判断A[start] A[end]与A[mid]的大小才能判断，target可能落在[start,mid]区间还是[mid,end]区间。

自己的代码实在有些繁琐丑陋，估计有些if else条件可以合并，后续会改进。