Python beat 100%! With explanation


  • 0
    X

    Apparently this is a variant of binary search. We still need to divide the array into 2 parts, but in a different condition judgement.

    class Solution(object):
        def search(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: int
            """
            L = len(nums)
            begin = 0
            end = L - 1
            mid = (begin + end)/2
            
            while 1:
                # when sub-array length is smaller then 3, just brute force (O(3))
                if end - begin <= 2:
                    if target == nums[begin]:
                        return begin
                    elif begin + 1 < L and target == nums[begin + 1]:
                        return begin + 1
                    elif begin + 2 < L and target == nums[begin + 2]:
                        return begin + 2
                    else:
                        return -1
                m = nums[mid]
                b = nums[begin]
                e = nums[end]
                if m == target:
                    return mid
                if b == target:
                    return begin
                if e == target:
                    return end
                
                # (the only) triky part. 
                if b > m:
                    if target < m or target > b:
                        begin = begin
                        end = mid - 1
                    elif target > m or target < b:
                        begin = mid + 1
                        end = end
               
                elif b < m:
                    if target < m and target > b:
                        begin = begin
                        end = mid - 1
                    else:
                        begin = mid + 1
                        end = end
                mid = (begin + end)/2
    

Log in to reply
 

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