81. Search in Rotated Sorted Array II

2020, Dec 05 2 mins read

1. Description

There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values).
Before being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]] (0-indexed). For example, [0,1,2,4,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,2,4,4].
Given the array nums after the rotation and an integer target, return true if target is in nums, or false if it is not in nums.

2. Example

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

3. Constraints

1 <= nums.length <= 5000
-10$^{4}$ <= nums[i] <= 10$^{4}$
nums is guaranteed to be rotated at some pivot.
-10$^{4}$ <= target <= 10$^{4}$

4. Follow Up

This problem is the same as Search in Rotated Sorted Array, where nums may contain duplicates. Would this affect the runtime complexity? How and why?

5. Solutions

Binary Search

n = i_nums.size()
Time complexity: O(n)
Space complexity: O(1)

class Solution {
public:
    bool search(const vector<int>& i_nums, int target) {
        for (int left = 0, right = i_nums.size() - 1; left <= right;) {
            int middle = left + (right - left) / 2;
            if (i_nums[middle] == target) {
                return true;
            }

            if (i_nums[left] < i_nums[right]) {
                return binary_search(i_nums.begin() + left, i_nums.begin() + right + 1, target);
            } else if (i_nums[left] == i_nums[middle]) {
                ++left;
            } else {
                bool pivotArray = i_nums[left] <= i_nums[middle];
                bool targetArray = i_nums[left] <= target;
                if (pivotArray ^ targetArray) {  // pivot and target exist in different parts
                    if (pivotArray) {  // pivot in the first, target in the second
                        left = middle + 1;
                    } else {  // target in the first, pivot in the second
                        right = middle - 1;
                    }
                } else {  // If pivot and target exist in same sorted array
                    if (i_nums[middle] < target) {
                        left = middle + 1;
                    } else {
                        right = middle - 1;
                    }
                }
            }
        }

        return false;
    }
};