63. 搜索旋转排序数组 II
中文English跟进“搜索旋转排序数组”,假如有重复元素又将如何?
是否会影响运行时间复杂度?
如何影响?
为何会影响?
写出一个函数判断给定的目标值是否出现在数组中。
样例
例1:
输入:
[]
1
输出:
false
例2:
输入:
[3,4,4,5,7,0,1,2]
4
输出:
true
输入测试数据 (每行一个参数)如何理解测试数据?
二分解法
大致思路:
1.寻找中枢点(最大值)
2.根据中枢点分为两个子数组,判断target在哪个子数组里面
3.在对应的排序好的子数组里面进行二分查找
class Solution: """ @param A: an integer ratated sorted array and duplicates are allowed @param target: An integer @return: a boolean """ def search(self, A, target): # write your code here #搜索旋转排序数组II #寻找中枢点,分两个子数组,二分查找 #寻找中枢点 if not A: return False #寻找中枢点 length = len(A) start, end = 0, length - 1 while start + 1 < end: #如果是升序的话,中枢点在另一边 mid = (start + end) // 2 #如果是升序,中枢点肯定在另一边 if (A[mid] < A[end]): end = mid elif (A[mid] > A[end]): start = mid else: #此时已经找到中枢点,为right,最小值 if end > 0 and A[end - 1] > A[end]: start = end - 1 #此时break或者不break均可以 break else: end -= 1 #取到的中枢点是最大值,也可以是最小值 pivot = start #分两个子数组 #如果是在0到pivot之间,则在这里面进行二分查找,否则的话,在另一边 if (A[0] <= target <= A[pivot]): left, right = 0, pivot + 1 else: left, right = pivot + 1, len(A) - 1 print(left, right) #二分查找 while left + 1 < right: mid = (left + right) // 2 if (target < A[mid]): right = mid else: left = mid #最终判断 if (A[left] == target) or (A[right] == target): return True return False