62. 搜索旋转排序数组
中文English假设有一个排序的按未知的旋转轴旋转的数组(比如,0 1 2 4 5 6 7
可能成为4 5 6 7 0 1 2
)。给定一个目标值进行搜索,如果在数组中找到目标值返回数组中的索引位置,否则返回-1。你可以假设数组中不存在重复的元素。
样例
例1:
输入: [4, 5, 1, 2, 3] and target=1,
输出: 2.
例2:
输入: [4, 5, 1, 2, 3] and target=0,
输出: -1.
挑战
O(logN) 时间限制
输入测试数据 (每行一个参数)如何理解测试数据?二分法思路:
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] <= target) and (target <= A[mid]): end = mid else: start = mid #如果左边存在降序,则在右边判断,mid不停的切分区间 else: #如果在mid和end区间,如果mid和end之间是升序的 if (A[mid] <= target) and (target <= 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)