81.Search in Rotated Sorted Array II

Tags: [sort], [binary_search], [trick]

Link: https://leetcode.com/problems/search-in-rotated-sorted-array-ii/#/description

Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e.,0 1 2 4 5 6 7might become4 5 6 7 0 1 2).

Write a function to determine if a given target is in the array.

The array may contain duplicates.

Solution: Binary Search, Trick

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: bool
        """
        if not nums or target is None:
            return False

        return self.search_helper(nums, 0, len(nums) - 1, target)

    def search_helper(self, nums, start, end, target):
        # base case
        if start > end:
            return False

        mid = start + (end - start) / 2
        if nums[mid] == target:
            return True

        if nums[start] < nums[mid]:
            # the sub array [start:mid + 1] is sorted.
            if nums[start] <= target < nums[mid]:
                return self.binary_search(nums, start, mid - 1, target)
            else:
                return self.search_helper(nums, mid + 1, end, target)
        elif nums[start] > nums[mid]:
            # the sub array [mid:end + 1] is sorted.
            if nums[mid] < target <= nums[end]:
                return self.binary_search(nums, mid + 1, end, target)
            else:
                return self.search_helper(nums, start, mid - 1, target)
        else:
            # nums[start] == nums[mid], cannot know which part is sorted.
            return self.search_helper(nums, start, mid - 1, target) or\
                   self.search_helper(nums, mid + 1, end, target)

    def binary_search(self, nums, start, end, target):
        while start <= end:
            mid = start + (end - start) / 2
            if nums[mid] == target:
                return True
            elif nums[mid] < target:
                start = mid + 1
            else:
                end = mid - 1

        return False

Revelation:

• When nums[start] == nums[mid], we cannot know which part is sorted, for example, the original nums = [1,1, 1, 1,1 1, 1, 2, 3], the rotated nums = [1, 1, 2, 3, 1, 1, 1, 1, 1], start = 0, end = 8, mid = 4, nums[start] = 1, nums[mid] = 1, but the sub array [start:mid + 1] is not sorted.

Note:

• Time complexity = O(n), n is the number of elements of the given nums.