81. Search in Rotated Sorted Array II Leetcode Python
Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Write a function to determine if a given target is in the array.
generally we can have two methods to do this problem, the first one is based on finding pivot and then divide the array into two parts, then search.
second one is still based on Binary search.
class Solution: # @param A a list of integers # @param target an integer # @return a boolean def search(self, A, target): if len(A) == 0: return False low = 0 high = len(A) - 1 while low < high: mid = low + (high - low) / 2 if A[mid] == target: return True if A[low] < A[mid]: if A[low] <= target < A[mid]: high = mid - 1 else: low = mid + 1 elif A[low] > A[mid]: if A[mid]< target <= A[high]: low = mid +1 else: high = mid -1 else: low += 1 if A[low] == target: return True return False
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。