81_Search in Rotated Sorted Array II

81. Search in Rotated Sorted Array II

Level: medium

Tag: array, binary search

Question

follow up of Q33 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 7 might become 4 5 6 7 0 1 2).
Write a function to determine if a given target is in the array.
The array may contain duplicates.

Example 1

Input: nums = [1, 2, 1, 1, 1]
       target = 2
Output: Ture

Idea (binary search)

Use the algorithm for Q33. Add one more test to avoid conner cases like example 1. Bad thing about example 1 is that when middle point is third integer, either half is sorted. We can further check if middle integer is the same as left and right. If yes, move left and right one step further.

Complexity

• Time:$O(logn)$
• Space:$O(1)$

Solution

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: bool
        """
        # pay attention: return is boolean not index

        left, right = 0, len(nums)-1

        while left <= right:
            mid = (left + right)//2
            if nums[mid] == target:
                return True

            # new tricky part (comparing with Q33 search in rotated sorted array)
            if nums[left] == nums[mid] == nums[right]:
                left += 1
                right -= 1
            # end of new tricky part

            elif nums[left] <= nums[mid]:
                # left half must be sorted
                # test if target is in left half
                if nums[left] <= target < nums[mid]:
                    # keep left half
                    right = mid - 1
                else:
                    # keep right half
                    left = mid + 1
            else:
                # right half must be sorted
                # test if target is in right half
                if nums[mid] < target <= nums[right]:
                    # keep right half
                    left = mid + 1
                else:
                    # keep left half
                    right = mid - 1
        return False