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


  • 0
    X

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

    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
    

Log in to reply
 

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