# AC Python code using binary search

• If the head equals the tail, we have to remove duplicates first (otherwise when the pointer gets to these duplicates, we don not know whether it belongs to left or right part). So the worst time complexity is O(n) in the case all elements are the same.

``````class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: bool
"""
n = len(nums)
if n == 0: return False
if target==nums[0]: return True
# remove duplicates if nums[0]==nums[n-1]
i, j = 0, n-1
if n>1 and nums[0]==nums[n-1]:
d = nums[0]
while i<j and nums[i]==d:   i += 1
i -= 1
while i<j and nums[j]==d:   j -= 1
j += 1
# modified bianry search
left = target>nums[i]
while i<=j:
k = (i+j)//2
if target==nums[k]: return True
elif (left and (nums[k]<target and nums[k]>=nums[0])) or (not left and not (nums[k]>target and nums[k]<nums[0])):    i = k+1
else:   j = k-1
return False
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.