62. 搜索旋转排序数组
2021-05-05 22:31
标签：put active get 旋转 mat lse 时间 位置 strong 假设有一个排序的按未知的旋转轴旋转的数组(比如， 例1: 例2: O(logN) 时间限制 二分法思路: 62. 搜索旋转排序数组 标签：put active get 旋转 mat lse 时间 位置 strong 原文地址：https://www.cnblogs.com/yunxintryyoubest/p/13191513.html62. 搜索旋转排序数组
0 1 2 4 5 6 7 可能成为4 5 6 7 0 1 2)。给定一个目标值进行搜索，如果在数组中找到目标值返回数组中的索引位置，否则返回-1。你可以假设数组中不存在重复的元素。样例
输入: [4, 5, 1, 2, 3] and target=1,
输出: 2.
输入: [4, 5, 1, 2, 3] and target=0,
输出: -1.
挑战
class Solution:
"""
@param A: an integer rotated sorted array
@param target: an integer to be searched
@return: an integer
"""
def search(self, A, target):
# write your code here
if not A: return -1
start, end = 0, len(A) - 1
while start + 1 end:
mid = (start + end) // 2
if (A[mid] == target):
return mid
#如果左边是升序的，在左边进行判断
if (A[start] A[mid]):
#如果在start和mid区间的话，如果start和mid中间是升序的，否则则else
if (A[start] A[mid]):
end = mid
else:
start = mid
#如果左边存在降序，则在右边判断，mid不停的切分区间
else:
#如果在mid和end区间,如果mid和end之间是升序的
if (A[mid] A[end]):
start = mid
else:
end = mid
#如果均不符合，则外面判断
if (A[start] == target):
return start
elif (A[end] == target):
return end
return -1
result = Solution().search([5,6,0,1,2,3,4],4)
print(result)