81. Search in Rotated Sorted Array II

• Difficulty: Medium

• Topics: Array, Binary Search

• Similar Questions:

  • Search in Rotated Sorted Array

Problem:

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 return true, otherwise return false.

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 nums may contain duplicates.
• Would this affect the run-time complexity? How and why?

Solutions:

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        return helper(nums, 0, nums.size() - 1, target);
    }

    bool helper(vector<int>& nums, int left, int right, int target) {
        if (left > right)   return false;
        if (left == right)  return nums[left] == target;
        int mid = left + (right - left)/2;
        if (nums[left] == nums[right] && nums[left] == nums[mid]) {
            return helper(nums, left, mid, target) || helper(nums, mid + 1, right, target);
        } else {
            if (nums[left] < nums[right]) {
                return target <= nums[mid] ? helper(nums, left, mid, target) : helper(nums, mid + 1, right, target);
            } else {
                if (nums[mid] >= nums[left]) {
                    if (target < nums[left] || target > nums[mid])  return helper(nums, mid + 1, right, target); 
                    else return helper(nums, left, mid, target);
                } else {
                    if (target > nums[mid] && target <= nums[right]) return helper(nums, mid + 1, right, target);
                    else return helper(nums, left, mid, target);
                }
            }
        }

    }
};