81. Search in Rotated Sorted Array II

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

(i.e.,[0,0,1,2,2,5,6]might become[2,5,6,0,0,1,2]).

You are given a target value to search. If found in the array returntrue, otherwise returnfalse.

Example 1:

Input: nums = [2,5,6,0,0,1,2], target = 0

Output: true

Example 2:

Input: nums = [2,5,6,0,0,1,2], target = 3

Output: false

Follow up:

• This is a follow up problem to Search in Rotated Sorted Array, where numsmay contain duplicates.

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

Thoughts:

1. only change is to consider case where both num[i] == num[j] == num[mid]: (i.e [3,1,2,3,3,3]), we should both update i and j by 1.

2. Selecting the pivot: then compare the mid value with the pivot to decide which side is monotuous

Code: T:(O(n) ~ O(logn));

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int i = 0;
        int j = nums.size()-1;
        while(i <= j){
            int mid = i + (j - i >> 1);
            if (nums[mid] == target) return true;

            if (nums[i] == nums[mid] && nums[j] == nums[mid]){i++; j--;}
            else if (nums[i] == nums[mid] && nums[j] != nums[mid]) i = mid + 1;

            else if(nums[i] < nums[mid]){
                if(nums[i] <= target and nums[mid] > target){
                    j = mid - 1;
                }
                else{
                    i = mid + 1;
                }
            }

            else if (nums[i] > nums[mid]){
                if (nums[mid] < target and nums[j] >= target){
                    i = mid + 1;
                }
                else{
                    j = mid - 1;
                }
            }

            else { 
                //
            }
    }

        return false;
    }
};

Python: Pivot

class Solution(object):
     def search(self, nums, target):
        # the most annoying case is duplicate pivoting value in the array!!!
        # [4,5,4,4,4,4,4]
        # [4,4,4,4,4,5,4]
        # when nums[mid] == pivot, it's impposible to decide whether you should move the 
        # lower bound or upper bound
        if not nums: return False
        pivot = nums[0]
        if target == pivot: return True

        # !!key!! 
        # we move lo and hi so pivot will never equal to lo or hi
        lo, hi = 0, len(nums) - 1
        while hi >= 0 and nums[hi] == pivot:
            hi -= 1
        while lo <= len(nums) - 1 and nums[lo] == pivot:
            lo += 1
        # now we can just blindly copy the code from search-in-rotated-sorted-array-i
        while lo <= hi:
            mid = (hi - lo) // 2 + lo
            if nums[mid] == target:
                return True
            if nums[mid] < pivot:
                # mid is on the upper side
                if nums[mid] < target < pivot:
                    lo = mid + 1
                else:
                    hi = mid - 1
            if nums[mid] > pivot:
                if pivot < target < nums[mid]:
                    hi = mid - 1
                else:
                    lo = mid + 1
        return False