Clear explanations for efficient solution


  • 0
    A

    Read below first (easier non-duplicate explanations):
    https://discuss.leetcode.com/topic/61986/clear-explanations-for-log-n-efficiency

    Recall valid inputs such as
    [0 1 2 4 5 6 7]
    [2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 4 5 6 7 0 1 2 2 2]

    1. Loop invariant: closed searching interval [low, high] must include target if it exists.
    2. Input may be ordered or ordered-drop-ordered. For either case, without duplicates, if nums[mid] <= nums[-1] (last element), right half is ordered, else left half is ordered. With duplicates, we should make this key condition still valid by moving initial low left-ward until != nums[-1]. This is possibly O(n).
    3. Ordered half enables constant-time check for whether target is in the ordered half ("nums[low] <= target < nums[mid]" or "nums[mid] < target <= nums[high]") or the other unordered half. Hence binary search is possible.
    class Solution(object):
        def search(self, nums, target):
            low = 0
            high = len(nums) - 1
            
            # Change part begin (comparing with non-duplication problem)
            # Make key condition still valid: if nums[mid] <= nums[-1], right half is ordered,
            # else left half is ordered.
            if len(nums) == 0:
                return False
            else:
                if nums[0] == target:
                    return True
                else:
                    # CARE: low may be out of range.
                    while low < len(nums) and nums[low] == nums[-1]:
                        low += 1
            # Change part end (comparing with non-duplication problem)
            
            while low <= high:
                mid = (high - low) / 2 + low
                if nums[mid] == target:
                    return True
                else:
                    # Right half is ordered.
                    if nums[mid] <= nums[-1]:
                        # Target is in right half.
                        if nums[mid] < target <= nums[high]:
                            low = mid + 1
                        # Target is in left half.
                        else:
                            high = mid - 1
                    # Left half is ordered.
                    else:
                        # Target is in left half.
                        if nums[low] <= target < nums[mid]:
                            high = mid - 1
                        # Target is in right half.
                        else:
                            low = mid + 1
            return False
    

Log in to reply
 

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