Topics › Binary Search › BS on 1D Arrays

Search in rotated sorted array-II

Medium TUF ID 88 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

An array of integers sorted in non-decreasing order, possibly with duplicates, was rotated at some unknown index. Given the rotated array nums and a target, return true if target is present and false otherwise. Because duplicates make the index ambiguous, the problem only asks for presence.

Constraints: 0 ≤ n ≤ 10^4, values and target fit in a 32-bit signed integer. The goal is to do as little work as possible; we will see that O(log n) is achievable on average but not in the worst case.

Example 1

nums = [2, 5, 6, 0, 0, 1, 2], target = 0
answer = true

Example 2

nums = [2, 5, 6, 0, 0, 1, 2], target = 3
answer = false            // 3 falls in the gap between 2 and 5

Example 3

nums = [1, 0, 1, 1, 1], target = 0
answer = true             // the classic case where the ends and the middle are all equal

Approach 1: Brute force, linear scan

Intuition. Look at every element. This remains the reference solution and, as we will see, its worst-case time cannot be beaten when duplicates are allowed.

Algorithm.

1. For each value v in nums: if v == target, return true.
2. Return false.

static boolean bruteForce(int[] nums, int target) {
    for (int v : nums) {
        if (v == target) return true;
    }
    return false;
}

Complexity. Time O(n), space O(1).

Approach 2: Optimal, binary search with a shrink step for duplicates

Intuition. In the distinct-values version we used the rule “if nums[lo] <= nums[mid], the left half [lo, mid] is sorted; otherwise the right half is”. We then checked whether target fits in the sorted half’s value range and moved accordingly.

With duplicates that rule can lie. Take Example 3, [1, 0, 1, 1, 1]: nums[lo] = 1, nums[mid] = 1, nums[hi] = 1. The test nums[lo] <= nums[mid] says “left half sorted”, but [1, 0, 1] is not sorted. The problem is that when nums[lo] == nums[mid] == nums[hi], both halves look identical from the outside and neither can be ruled out.

The fix is small. In that exact situation we know one more thing: nums[mid] != target (we just checked), hence nums[lo] != target and nums[hi] != target. So we can safely discard the two end elements with lo++, hi-- and try again. The information we lacked was about the ends, and the ends are precisely what we are allowed to throw away.

When the three values are not all equal, the old rule is correct again. Suppose nums[lo] <= nums[mid]. If the drop were inside (lo, mid], then nums[mid] would be in the smaller run and nums[lo] in the larger run, so nums[mid] <= nums[hi] <= nums[lo]. Combined with nums[lo] <= nums[mid] this forces all three to be equal, which we have excluded. Therefore the left half really is sorted. The mirror argument covers nums[lo] > nums[mid].

Algorithm.

1. lo = 0, hi = n - 1.
2. While lo <= hi:
   • mid = lo + (hi - lo) / 2. If nums[mid] == target, return true.
   • If nums[lo] == nums[mid] and nums[mid] == nums[hi]: lo++, hi--, continue.
   • If nums[lo] <= nums[mid] (left half sorted): if nums[lo] <= target < nums[mid], hi = mid - 1; else lo = mid + 1.
   • Else (right half sorted): if nums[mid] < target <= nums[hi], lo = mid + 1; else hi = mid - 1.
3. Return false.

static boolean optimal(int[] nums, int target) {
    int lo = 0, hi = nums.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] == target) return true;
        if (nums[lo] == nums[mid] && nums[mid] == nums[hi]) {   // cannot tell which half is sorted
            lo++;                                                // both ends equal nums[mid] != target,
            hi--;                                                // so dropping them loses nothing
            continue;
        }
        if (nums[lo] <= nums[mid]) {                                  // left half [lo, mid] is sorted
            if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
            else lo = mid + 1;
        } else {                                                      // right half [mid, hi] is sorted
            if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
            else hi = mid - 1;
        }
    }
    return false;
}

Dry run on nums = [1, 0, 1, 1, 1], target = 0:

On nums = [2, 5, 6, 0, 0, 1, 2], target = 0, the very first probe is mid = 3 with nums[3] = 0, so the method returns true in one step. It is instructive to see why the equality check has to come before the half logic. The range tests nums[lo] <= target < nums[mid] and nums[mid] < target <= nums[hi] deliberately exclude nums[mid], so if the equality check were missing the search would run like this:

and wrongly report false. Checking nums[mid] == target first is not an optimisation; it is part of the correctness argument.

Complexity. Time O(log n) on average and in all inputs without long runs of equal values; O(n) in the worst case. Space O(1).

The worst case is real, not a weakness of this particular code. Consider [1, 1, 1, 1, 1, 1, 1] with one 2 hidden somewhere, say at index k, and target = 2. Every probe that does not hit index k sees nums[lo] == nums[mid] == nums[hi] == 1 and learns nothing about where the 2 is. Any algorithm that reads fewer than about n / 2 positions can be fooled by placing the 2 in an unread position, so Ω(n) comparisons are necessary in the worst case. The shrink step costs one iteration per discarded pair of elements, which is why the running time degrades to linear exactly in those inputs and stays logarithmic otherwise.

Edge cases and pitfalls

• All elements equal, target absent. [1, 1, 1, 1, 1], target = 2: the shrink step fires every time until lo > hi, returning false after about n / 2 iterations.
• All elements equal, target present. The first probe hits, true in one step.
• Minimum hidden on either side of mid. [1, 0, 1, 1, 1] and [1, 1, 1, 0, 1] are both tested; the shrink step is what lets the search recover.
• Not rotated / one or two elements / empty. Behave exactly as in the distinct version; the empty array skips the loop.
• Shrinking only one side. Some solutions do only lo++. That is still correct but slower in the all-equal case; dropping both ends is justified because both equal nums[mid].
• Skipping the equality check. The range tests exclude nums[mid], so nums[mid] == target must be checked first (see the second dry run).
• Forgetting continue. Without it the code would fall through into the half logic with the old mid, which is based on indices that just changed.
• Overflow in mid. Use lo + (hi - lo) / 2.

Related problems

• Search in rotated sorted array-I is the distinct-values version; read it first for the sorted-half argument.
• Find minimum in Rotated Sorted Array uses the same nums[mid] versus nums[hi] comparison and faces the same duplicate problem in its own follow-up.
• Search X in sorted array is the unrotated, duplicate-free baseline.