LintCode Q63 Search in Rotated Sorted Array II in Python

  • Jinhai ZHOU
  • 4 Minutes
  • 2016年12月28日
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
"""
@param A : an integer ratated sorted array and duplicates are allowed
@param target : an integer to be searched
@return : a boolean
"""
def search(self, A, target):
# write your code here
if len(A) == 0:
return False
lo, hi = 0, len(A) - 1
return self.binarySearch(A, lo, hi, target)
def binarySearch(self, A, lo, hi, target):
if lo > hi:
return False
[left, right] = [False, False]
if lo <= hi:
mid = lo + (hi - lo)/2
if A[mid] == target:
return True
elif A[mid] == A[lo] and A[mid] == A[hi]:
left = self.binarySearch(A, lo, mid - 1, target)
right = self.binarySearch(A, mid + 1, hi, target)
elif (A[lo] < A[mid] and A[lo] <= target and target < A[mid]) or (A[mid] < A[lo] and not (A[mid] < target and target <= A[hi])):
left = self.binarySearch(A, lo, mid - 1, target)
else:
right = self.binarySearch(A, mid + 1, hi, target)
return right | left
知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。