81. Search in Rotated Sorted Array II

Information

  • Diffculty: Medium

  • Created: 2020-03-10 08:27:00

  • Last Motified: 2020-03-10 08:49:08

  • Tags: Array, Binary Search

Intuition

We could use a binary search to check if the target exist in the array.

Generally, if nums[lo] != nums[hi] or nums[lo] == nums[hi] != nums[mid], we could always easily know target should be in nums[lo:mid] or nums[mid:hi]. But if nums[lo] == nums[mid] == nums[hi] (e.g. [1, 1, 1, 3, 1]), there is no way to directly know target is in which part. So in this case, we should both search the left part and the right part.

Solution

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        if not nums:
            return False
        if nums[0] == target or nums[-1] == target:
            return True
        return self._helper(0, len(nums) - 1, nums, target)

    def _helper(self, lo, hi, nums, target):
        if hi - lo <= 1:
            return False

        mid = (hi + lo) // 2
        if nums[mid] == target:
            return True
        elif nums[lo] == nums[hi] == nums[mid]:
            return self._helper(lo, mid, nums, target) or \
                self._helper(mid, hi, nums, target)
        elif nums[lo] <= nums[mid]:
            if nums[lo] <= target <= nums[mid]:
                return self._helper(lo, mid, nums, target)
            else:
                return self._helper(mid, hi, nums, target)
        else:
            if nums[mid] <= target <= nums[hi]:
                return self._helper(mid, hi, nums, target)
            else:
                return self._helper(lo, mid, nums, target)