LeetCode //C - 81. Search in Rotated Sorted Array II

81. Search in Rotated Sorted Array II

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.

You must decrease the overall operation steps as much as possible.
 

Example 1:

Example 2:

Constraints:

• 1 <= nums.length <= 5000
• − 1 0 4 < = n u m s [ i ] < = 1 0 4 -10^4 <= nums[i] <= 10^4 −104<=nums[i]<=104
• nums is guaranteed to be rotated at some pivot.
• − 1 0 4 < = t a r g e t < = 1 0 4 -10^4 <= target <= 10^4 −104<=target<=104

From: LeetCode
Link: 81. Search in Rotated Sorted Array II

---

Solution:

Ideas:

1. Initialization:
   We start with two pointers, left and right, which are set to the beginning and end of the array, respectively.

2. Main Loop:
   The main part of the function is a loop that continues until the left pointer is greater than the right pointer, which means the entire array has been examined.

3. Mid-point Calculation:
   Inside the loop, a mid pointer is calculated as the average of left and right, which effectively splits the array into two halves.

4. Direct Target Check:
   If the element at the mid index matches the target, the function immediately returns true indicating that the target has been found.

5. Handling Duplicates:
   If the elements at the indices left, mid, and right are the same, it’s unclear which side of mid is sorted. This ambiguity is resolved by incrementally moving the left pointer rightward and the right pointer leftward. This step helps in slowly reducing the search range while handling duplicates that could skew the identification of sorted sections.

6. Identify Sorted Half:
   If the left part of the array (from left to mid) is in sorted order (i.e., nums[left] is less than or equal to nums[mid]):
   Check if the target lies within this range. If so, adjust the right pointer to mid - 1.
   If not, adjust the left pointer to mid + 1.
   If the left part is not sorted, then the right part must be sorted:
   Check if the target lies within the right half (from mid to right). If so, adjust the left pointer to mid + 1.
   If not, adjust the right pointer to mid - 1.

7. Return False:
   If the loop exits without finding the target, the function returns false, indicating that the target is not present in the array.

Code:

bool search(int* nums, int numsSize, int target) {
    int left = 0, right = numsSize - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        // Check if the target is found
        if (nums[mid] == target) {
            return true;
        }
        
        // When left, mid, and right are the same, reduce ambiguity
        if (nums[left] == nums[mid] && nums[right] == nums[mid]) {
            left++;
            right--;
        } else if (nums[left] <= nums[mid]) {
            // Left side is sorted
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else {
            // Right side is sorted
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    return false;
}