Search in Rotated Sorted Array II

Problem Statement:

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:

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
• -10^4 <= nums[i] <= 10^4
• nums is guaranteed to be rotated at some pivot.
• -10^4 <= target <= 10^4

Follow up: This problem is similar to Search in Rotated Sorted Array, but numsmay contain duplicates. Would this affect the runtime complexity? How and why?

Solution:

• Same as Search in Rotated Sorted Array, just one condition to handle dups. Check the comment in code.

class Solution {
    public boolean search(int[] nums, int target) {
        int start = 0;
        int end = nums.length - 1;
 
        while (start <= end) {
            int mid = start + (end - start) / 2;
 
            if (nums[mid] == target) {
                return true;
            }
            /*
             * Handle duplicates
             * The only difference is that due to the existence of duplicates,
             * arr[l] == arr[mid] could be possible, the first half could be out of order
             * (i.e. not in the ascending order, e.g. {3, 1, 2, 3, 3, 3, 3})
             * we have to deal this case separately.
             * In that case, it is guaranteed that arr[high] also equal to arr[mid]
             */
            if (nums[start] == nums[mid] && nums[mid] == nums[end]) {
                end--;
                start++;
            } else if (nums[start] <= nums[mid]) { // check if left is sorted
                if (nums[start] <= target && target < nums[mid]) {
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            } else { // right array must be sorted
                if (target <= nums[end] && nums[mid] < target) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
        }
        return false;
    }
}

Note

Why Duplicates Affect Runtime

• In a typical binary search, the algorithm relies on the ability to halve the search space based on comparisons.
• However, when duplicates are present, especially when nums[start], nums[mid], and nums[end] are equal, the algorithm cannot conclusively determine which half of the array is sorted or where the target might lie.
• This necessitates incrementing start or decrementing end, effectively reducing the problem size by only one element rather than halving it.

Worst-Case Scenario - TC: O(n)

• In the worst case, if the array consists of many duplicate elements, and these elements align such that nums[start] == nums[mid] == nums[end], the algorithm might end up checking each element linearly.