AC Python code using binary search


  • 0
    H

    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
    

Log in to reply
 

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