# Since there is not much Python solution. Average O(log) worst O(N).

• The point is that you just need to make really tiny modification on your search rotated array I code.

``````class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: bool
"""
L = len(nums)
begin = 0
end = L - 1
mid = (begin + end)/2

while begin <= end:
if nums[mid] == target: return True
elif nums[begin] == target: return True
elif nums[end] == target: return True

if nums[begin] > nums[mid]:
if target < nums[mid] or target > nums[begin]:
begin = begin
end = mid - 1
mid = (begin + end)/2
else:
begin = mid+1
end = end
mid = (begin + end)/2
elif nums[end] < nums[mid]:
if target < nums[mid] and target > nums[begin]:
begin = begin
end = mid - 1
mid = (begin + end)/2
else:
begin = mid + 1
end = end
mid = (begin + end)/2
# this else is the only modified part. i.e., when nums[begin] == nums[mid] or nums[end] == nums[mid], you hve no idea if we should search for left side or right side. Only in this case should you use linear search.
# To my understanding the average complexity should still be O(log)
else:
return target in nums[begin:end+1]
return False
``````

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