Share my recursive and iterative Python solution with detailed explanation, O(n) worst case


  • 1
    D

    The idea is simple. Use binary search. Let H, M and T be the number at head, middle and tail, respectively.

    1. H == M == T: target could be in either half, we need to search both half

    2. otherwise we can continue binary search, just find the right half. If the order pattern is any of the following ones, the target must be in the upper half if it exists, otherwise lower half

    a. H <= M < Target : H to M is sorted and target is bigger than M (biggest in lower half)

    b. Target < H <= M; H to M is sorted and target is smaller than H (smallest in lower half)

    c. T >= Target > M: M to T is sorted and target is within range

    Recursive one

    class Solution:
        # @param {integer[]} nums
        # @param {integer} target
        # @return {boolean}
        def search(self, nums, target):
            def searchHelper(nums, head, tail, target):
                if head > tail:
                    # does not exist
                    return False
                middle = (head + tail)//2
                if nums[middle] == target:
                    return True
                if nums[head] == nums[tail] == nums[middle]:
                    # worst case, target could be in either half
                    return (searchHelper(nums, head, middle-1, target) or searchHelper(nums, middle, tail-1, target))
                if (nums[head] <= nums[middle] < target) or (target < nums[head] <= nums[middle]) or (nums[tail] >= target > nums[middle]):
                    return searchHelper(nums, middle+1, tail, target)
                return searchHelper(nums, head, middle-1, target)
            return searchHelper(nums, 0, len(nums)-1, target)
    

    Iterative one:

    class Solution:
        # @param {integer[]} nums
        # @param {integer} target
        # @return {boolean}
        def search(self, nums, target):
            head, tail = 0, len(nums) - 1
            while head <= tail:
                middle = (head + tail)//2
                if nums[middle] == target:
                    return True
                if nums[head] == nums[tail] == nums[middle]:
                    # worst case, target could be in either half, move tail by one step
                    tail -= 1
                elif (nums[head] <= nums[middle] < target) or (target < nums[head] <= nums[middle]) or (nums[tail] >= target > nums[middle]):
                    # target must be in the upper half if it exists
                    head = middle + 1
                else:
                    # target must be in the lower half if it exists
                    tail = middle - 1
            return False

Log in to reply
 

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