81. Search in Rotated Sorted Array II

# Medium

Solution 1:

1. Keep one of them when having repeated elements at the beginning and end of the list

2. Look for the pivot, which is to find the first pivot position. (In order to deal with two situations on time: it's an ascending list, it's a rotated list, always compare mid and left first which means keep the left side is an ascending list.)

3. Do binary search according to above two situations

4. Consider the edge case: 0 element

[6,8,5,5,5] and [6,8,9,9,9]

[5,5,5,4] and [4,5,5,5]

When looking for the pivot, if value(mid) = value(left), keep right side

while left + 1 < right:
    mid = left + (right - left)//2
    if nums[mid] >= nums[left]:
        left = mid
    else:
        right = mid
pivot = right

Judging the list is an ascending or rotated list according to comparison of nums[left] and nums[right], then do binary search at the same time

Time complexity: Because we can't confirm time complexity of step1. The worst case is $T=O(n)$ . Except that step, time complexisty = $O(lgN)$

Solution 2:

1. remove the repeated elements from start and end

2. find the pivot, consider three cases

3. search the target, consider three cases

// Python
class Solution:
    def search(self, nums: List[int], target: int) -> bool: 
        # remove the some elements of begining and end
        start = 0
        for i in range(len(nums)-1):
            if nums[i] != nums[i+1]:
                break
            else:
                start = start + 1
                
        end = len(nums) - 1
        for i in reversed(range(1, len(nums))):
            if nums[i] != nums[i-1]:
                break
            else:
                end = end - 1
                
        if start >= end:   # [0, 0, 0, 0]
            if target == nums[start]:
                return True
            else:
                return False
                
        # find the pivot
        left = start
        right = end
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] ==  nums[right]:
                right = mid
            elif nums[mid] < nums[right]:
                right = mid
            else:
                left = mid + 1
        
        # search the target
        pivot = left
        if target >= nums[pivot] and target <= nums[end]:
            start = pivot
        else:
            end = pivot
        
        while start <= end:
            mid = start + (end - start) // 2
            if nums[mid] == target:
                return True
            if nums[mid] < target:
                start = mid + 1
            else:
                end = mid - 1
                
        return False

Solutioin 3 (Java one-pass):

1. remove same element from end, such as [4, 4, 5, 1, 3, 4, 4] -> [4, 4, 5, 1, 3]

2. Same as #33, two cases: [start, end] is rotated; [start, end] is not rotated

// java efficient one-pass
class Solution {
    public boolean search(int[] nums, int target) {
        // remove same element from end
        int end = nums.length - 1;
        // at least keep one element
        while(end > 0) {
            if(nums[end] != nums[0])
                break;
            end --;
        }
        
        int start = 0;
        while(start <= end) {
            int mid = start + (end - start)/2;
            if(nums[mid] == target)
                return true;
            // [start, end] not rotated
            else if(nums[mid] >= nums[start]) {
                if(target < nums[mid] && target >= nums[start])
                    end = mid - 1;
                else
                    start = mid + 1;                
            }
            // [start, end] is rotated
            else {
                if(target > nums[mid] && target <= nums[end])
                    start = mid + 1;
                else
                    end = mid - 1;
            }
        }
        
        return false;
    }
}java