081.SearchInRotatedSortedArrayII.md

tags: Array, Binary Search

#LeetCode 81 Search in Rotated Sorted Array II

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

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

Write a function to determine if a given target is in the array. (return true if exists otherwise false)

Diffculty
Medium

Similar Problems
[LeetCode 33] Search in Rotated Sorted Array

Analysis

This is similar to the problem Search in Rotated Sorted Array, the only place that we need to modify is when nums[mid] == nums[low], we should set low++, in this case, we aren't be able to know whether the part is in order, consider :

 1   1   1   3  1
 ^       ^
low     mid

 1   3   1   1  1
 ^       ^
low     mid

As show above, when nums[mid] == nums[low], we can't be sure which part is in order, so we just increase low.

The time complexity will be up to O(n) in worst case (all numbers are equal).

Solutions

1. Cpp Solution

class Solution {
public:
    int search(vector<int> &nums, int target) {
        int low = 0, high = nums.size() - 1;
        while (low <= high) {
            const int mid = low + (high - low) / 2;

            if (nums[mid] == target)
                return true;

            if (nums[low] == nums[mid]) {  // Important
                low++;
            } else if (nums[low] < nums[mid]) {
                if (nums[low] <= target && target < nums[mid])
                    high = mid - 1;
                else
                    low = mid + 1;
            } else {
                if (nums[mid] < target && target <= nums[high])
                    low = mid + 1;
                else
                    high = mid - 1;
            }
        }
        return false;
    }
};

2. Go Solution

func search(nums []int, target int) bool {
    low, high := 0, len(nums)-1

    for low <= high {
        mid := low + (high-low)/2
        if nums[mid] == target {
            return true
        } else {
            if nums[low] == nums[mid] {
                low += 1
            } else if nums[low] < nums[mid] {
                if nums[low] <= target && target < nums[mid] {
                    high = mid - 1
                } else {
                    low = mid + 1
                }
            } else {
                if nums[mid] < target && target <= nums[high] {
                    low = mid + 1
                } else {
                    high = mid - 1
                }
            }
        }
    }

    return false
}

Reference