Search in Rotated Sorted Array II

Problem Statement

Consider an integer array nums which was initially sorted in non-decreasing order. This array undergoes a modification where it is rotated around an unknown pivot index k (0 <= k < nums.length). This operation alters the sequence such that part of the array following the pivot moves to the front, while the rest of the array shifts towards the end. As a result, nums gets transformed into [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]].

For instance, the array [0,1,2,4,4,4,5,6,6,7] might be rotated at pivot index 5 to produce [4,5,6,6,7,0,1,2,4,4].

After this transformation, you are provided the rotated array nums and an integer target. The task is to determine whether the target exists in the modified array nums. The response should be true if the target is found and false otherwise. The aim is to achieve this with the minimal number of operations to ensure efficient execution, especially under constraints where array size can be large.

Examples

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

Constraints

• 1 <= nums.length <= 5000
• -104 <= nums[i] <= 104
• nums is guaranteed to be rotated at some pivot.
• -104 <= target <= 104

Approach and Intuition

To effectively determine the presence of target in the rotated array nums, follow these steps:

1. Identify Rotation Index:

   • This step involves finding the index at which the original sorted array was rotated. This can be done using a modified binary search that looks for the point where a disorder (a drop) in the value sequence occurs.

2. Binary Search Implementation:

   • Depending on the value of the target and its comparison with the starting elements of the possibly two sorted subarrays in nums (since a rotation results in at most two sorted portions), decide which segment of the array to apply binary search on.
   • If target is greater than the start of the first segment or less than the start of the second segment, you know it must be in the first sorted portion if present. Otherwise, check the second.

3. Edge Case Consideration for Duplicates:

   • When nums contains duplicates, the classic binary search needs a slight modification to handle cases where mid-values repeat (for example, having multiple contiguous occurrences of an element). In such cases, simply repeating identical elements should not incorrectly influence the direction of search.

Example Calculations from Given Inputs:

• In the example where nums = [2,5,6,0,0,1,2] and target = 0, the array is split due to the rotation, and 0 falls within the second subarray that starts after the highest number (6). By selectively searching within the appropriate segment, efficient retrieval is ensured, returning true.
• When target = 3 for the same nums, neither sub-array (analyzed as explained) contains the number 3. Thus, confirming its absence with minimal checks leads to a result of false.

By breaking down the search space based on known properties of sorted arrays and the introduced rotation disruption, the problem's complexity can be managed more effectively even as the size of the data scales.

Solutions

class Solution {
public:
    bool searchElement(vector<int>& arr, int target) {
        int size = arr.size();
        if (size == 0) return false;
        int left = 0;
        int right = size - 1;
    
        while (left <= right) {
            int mid = left + (right - left) / 2;
    
            if (arr[mid] == target) {
                return true;
            }
    
            if (!canOptimizeSearch(arr, left, arr[mid])) {
                left++;
                continue;
            }
    
            // Determine the arrays the pivot and target belong to
            bool pivotInFirst = isPivotInFirst(arr, left, arr[mid]);
            bool targetInFirst = isPivotInFirst(arr, left, target);
            if (pivotInFirst ^ targetInFirst) {
                if (pivotInFirst) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            } else {
                if (arr[mid] < target) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return false;
    }
    
    bool canOptimizeSearch(vector<int>& arr, int start, int val) {
        return arr[start] != val;
    }
    
    bool isPivotInFirst(vector<int>& arr, int start, int val) {
        return arr[start] <= val;
    }
};