首页 > 代码库 > leetcode 【 Search in Rotated Sorted Array 】python 实现
leetcode 【 Search in Rotated Sorted Array 】python 实现
题目：
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]<A[mid]:33 start = mid+134 elif A[start]<A[mid] and A[end]<A[mid]:35 if 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]:45 end = mid-146 elif A[start]<A[mid] and A[end]<A[mid]:47 start = mid+148 elif A[start]>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条件可以合并，后续会改进。
leetcode 【 Search in Rotated Sorted Array 】python 实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。