Search in Rotated Sorted Array II

You are given an integer array, nums, sorted in non-decreasing order (values can repeat). Before being given to your function, nums was rotated at some unknown pivot index k (where 0 ≤ k < nums.length).

Search in Rotated Sorted Array II (With Duplicates)

Problem Statement

You are given an integer array, nums, sorted in non-decreasing order (values can repeat).

Before being given to your function, nums was rotated at some unknown pivot index k (where 0 ≤ k < nums.length). This means the array is rearranged like this:

[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]

For example, [0, 1, 2, 4, 4, 4, 5, 6, 6, 7] rotated at pivot index 5 becomes [4, 5, 6, 6, 7, 0, 1, 2, 4, 4].

Given the rotated array and an integer target, return true if target is somewhere in nums, or false if it is not.

You should try to reduce the number of steps your solution takes as much as possible.

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

Solution

This problem is very similar to the regular Search in Rotated Sorted Array problem. We check which half of the array is sorted, and see if target falls inside that sorted half.

The key difference here is that this array can have duplicate values. Because of this, we can't always tell which side is sorted just by comparing nums[start], nums[mid], and nums[end] — sometimes these three values can all be equal, which makes it impossible to know which side is truly sorted.

Handling Duplicates

• If nums[start], nums[mid], and nums[end] are all equal, we can't tell which side is sorted. In this case, we simply shrink the search range slightly, by moving start forward and end backward by one. This removes the ambiguous edge values without skipping over any real answers.

The Rest of the Logic

• If nums[mid] is greater than or equal to nums[start], the left half is sorted:
  • If target falls between nums[start] and nums[mid], search the left half.
  • Otherwise, search the right half.
• Otherwise, the right half is sorted:
  • If target falls between nums[mid] and nums[end], search the right half.
  • Otherwise, search the left half.
• We repeat this until we either find the target, or the search range becomes empty.

Code

var search = function (nums, target) {
    let start = 0;
    let end = nums.length - 1;

    while (start <= end) {
        let mid = start + Math.floor((end - start) / 2);

        if (nums[mid] === target) return true;

        if (nums[start] === nums[mid] && nums[mid] === nums[end]) {
            start++;
            end--;
            continue;
        }

        // look which side is sorted
        if (nums[mid] >= nums[start]) {
            if (target < nums[mid] && target >= nums[start]) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        } else {
            if (target <= nums[end] && nums[mid] < target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
    }

    return false;
};