```
class Solution:
# @param A a list of integers
# @param target an integer
# @return a boolean
def binSearch(self,A,target):
low=0
high=len(A)-1
while True:
if low>high:
return -1
mid=low+(high-low)/2
if target<A[mid]:
high=mid-1
elif target>A[mid]:
low=mid+1
else:
return mid
def findPivot(self,A):
low=0
high=len(A)-1
while low<high:
mid=low+(high-low)/2
while A[mid]==A[high] and mid!=high:
high=high-1
while A[mid]==A[low] and low!=mid:
low=low+1
if A[mid]<=A[high]:
high=mid
else:
low=low+1
return low
def search(self, A, target):
if len(A)==0 or (len(A)==1 and A[0]!=target):
return False
pivot=self.findPivot(A)
left=A[:pivot]
right=A[pivot:]
if self.binSearch(left,target)==-1 and self.binSearch(right,target)==-1:
return False
else:
return True
```