Search in Rotated Sorted Array II — Handle Duplicates with Binary Search [LC 81]

Problem Statement#

LeetCode 81 — Search in Rotated Sorted Array II · Difficulty: Medium

There is an integer array nums sorted in non-decreasing order (may contain duplicates). The array was rotated at an unknown pivot index. Given nums and a target, return true if target exists in nums, or false otherwise.

Constraints:

• 1 <= nums.length <= 5000
• -10^4 <= nums[i], target <= 10^4
• nums is guaranteed to be rotated at some pivot (possibly 0 — no rotation)

Example 1:

Input:  nums = [2,5,6,0,0,1,2], target = 0
Output: true
Explanation: 0 appears at indices 3 and 4.

Example 2:

Input:  nums = [2,5,6,0,0,1,2], target = 3
Output: false
Explanation: 3 is not in the array.

Example 3:

Input:  nums = [1,0,1,1,1], target = 0
Output: true
Explanation: Duplicates force a linear scan of the ambiguous boundary region.

Why This Problem Matters#

This is the direct FAANG follow-up to LC 33 (Search in Rotated Sorted Array). Google, Amazon, and Meta frequently extend their binary search interview questions with duplicates to test whether candidates can handle edge cases robustly — not just recite templates.

The critical skill being tested: recognising when a standard technique degrades, and articulating why. Duplicates introduce an ambiguous case that breaks the core guarantee of binary search on rotated arrays. The lo++ shrink is the elegant, correct response — and being able to explain why it is safe, why it costs worst-case O(n), and when that scenario actually occurs is exactly what separates a strong candidate from a weak one.

If you have already solved LC 33 and LC 153, this problem teaches you the remaining piece: what happens at the boundary between "deterministic binary search" and "necessary linear degradation."

The Core Insight#

In LC 33 (no duplicates), when nums[lo] <= nums[mid], the left half is guaranteed sorted. With duplicates, nums[lo] == nums[mid] is ambiguous:

• [1, 1, 2, 1, 1] — left half [1,1,2] is sorted, nums[lo] == nums[mid] == 1
• [1, 2, 1, 1, 1] — left half [1,2,1] is NOT sorted, nums[lo] == nums[mid] == 1

Both arrays have nums[lo] == nums[mid]. We cannot determine which half is sorted without scanning further.

The fix: when nums[lo] == nums[mid], increment lo by 1. This safely eliminates one element that is NOT the unique pivot. It costs one element per iteration in the worst case — hence O(n) worst case — but the algorithm remains correct because we never discard the target.

Decision tree at each step:

1. nums[mid] == target → return true
2. nums[lo] == nums[mid] → ambiguous, do lo++ (safe shrink)
3. Left half sorted (nums[lo] < nums[mid]): check if target is in [nums[lo], nums[mid]), shrink accordingly
4. Right half sorted (nums[mid] < nums[lo]): check if target is in (nums[mid], nums[hi]], shrink accordingly

Visual Dry Run#

Example 1: nums = [2, 5, 6, 0, 0, 1, 2], target = 0

Example 2 (tricky): nums = [1, 3, 1, 1, 1], target = 3

Worst case: nums = [1, 1, 1, 1, 1], target = 2

Every iteration hits nums[lo] == nums[mid], so lo++ fires each time — O(n) linear scan, returns false.

Common Mistakes#

1. Copying LC 33 verbatim — LC 33 uses nums[lo] <= nums[mid] to detect a sorted left half. With duplicates this fires even when the left half is NOT sorted, leading to wrong answers or infinite loops.

2. Using nums[lo] == nums[mid] == nums[hi] as the only trigger — some solutions only shrink when all three endpoints match. This is unnecessarily restrictive; the simpler nums[lo] == nums[mid] check covers all ambiguous cases and is cleaner.

3. Doing hi-- on the wrong side — if you shrink hi instead of lo for the ambiguous case, you must be consistent. Mixing lo++ and hi-- for different cases causes bugs. Pick one direction and apply it consistently.

4. Not handling all-same arrays — [2, 2, 2, 2] with target = 3 must return false after a full linear scan. Test your implementation against this.

5. Off-by-one in sorted-half boundary check — the condition checking if target is in the left half is nums[lo] &lt;= target < nums[mid]. The strict < on the mid side is critical — nums[mid] is already checked separately at the top of the loop.

6. Claiming O(log n) always — a key interview point is that worst case degrades to O(n). If you claim O(log n) always, the interviewer will probe with [1,1,1,1,0,1] and you will have to backtrack. State the trade-off proactively.

7. Forgetting the continue after lo++ — if you increment lo but forget to continue, the code falls through into the sorted-half logic with stale values, producing wrong decisions.

Solutions#

Python#

def search(nums: list[int], target: int) -> bool:
    lo, hi = 0, len(nums) - 1          # inclusive boundaries
 
    while lo <= hi:
        mid = lo + (hi - lo) // 2      # safe midpoint, avoids overflow
 
        if nums[mid] == target:         # direct hit — target found
            return True
 
        # Ambiguous case: duplicates prevent us from knowing which half is sorted.
        # Safely shrink lo by 1. We lose at most one element per iteration.
        if nums[lo] == nums[mid]:
            lo += 1
            continue                    # re-evaluate with updated lo
 
        if nums[lo] < nums[mid]:
            # Left half [lo..mid] is sorted (strict inequality guarantees it)
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1           # target must be in the sorted left half
            else:
                lo = mid + 1           # target is in the rotated right half
        else:
            # Right half [mid..hi] is sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1           # target must be in the sorted right half
            else:
                hi = mid - 1           # target is in the rotated left half
 
    return False                        # search space exhausted, target not found

JavaScript#

function search(nums, target) {
    let lo = 0, hi = nums.length - 1;  // inclusive boundaries
 
    while (lo <= hi) {
        const mid = lo + Math.floor((hi - lo) / 2); // safe midpoint
 
        if (nums[mid] === target) return true;        // target found
 
        // Ambiguous duplicate at left boundary — cannot determine sorted half.
        // Shrink lo by 1. This is always safe: we never skip the target.
        if (nums[lo] === nums[mid]) {
            lo++;
            continue;                   // restart loop with updated lo
        }
 
        if (nums[lo] < nums[mid]) {
            // Left half is guaranteed sorted
            if (nums[lo] <= target && target < nums[mid]) {
                hi = mid - 1;          // target in sorted left half
            } else {
                lo = mid + 1;          // target in rotated right half
            }
        } else {
            // Right half is guaranteed sorted
            if (nums[mid] < target && target <= nums[hi]) {
                lo = mid + 1;          // target in sorted right half
            } else {
                hi = mid - 1;          // target in rotated left half
            }
        }
    }
 
    return false;                       // target not found
}

Complexity Analysis#

The O(n) worst case only occurs when every element is identical, forcing lo++ on every iteration. For typical real-world rotated arrays with occasional duplicates, the algorithm behaves as O(log n).

Follow-up Questions#

1. How does this differ from LC 33? — LC 33 has no duplicates, so nums[lo] <= nums[mid] always means left is sorted. Here, nums[lo] == nums[mid] is ambiguous and requires the lo++ escape hatch.

2. Can we always solve it in O(log n)? — No. The input [1, 1, 1, ..., 1, 0, 1] fundamentally requires a linear scan in the worst case. This is provably optimal for this problem class.

3. What if we use hi-- instead of lo++? — Equally correct. Both shrink the search space by exactly 1 in the ambiguous case. Prefer lo++ if you compare against lo, and hi-- if you compare against hi.

4. How does this relate to LC 154 (Find Minimum in Rotated Sorted Array II)? — Same hi-- trick when nums[mid] == nums[hi] makes it ambiguous which side has the minimum.

5. What if the array is not rotated at all? — The algorithm handles it correctly. If no rotation occurred, nums[lo] <= nums[mid] always, and we reduce to standard binary search.

This Pattern Solves#

• LC 33 — Search in Rotated Sorted Array (no duplicates, guaranteed O(log n))
• LC 81 — Search in Rotated Sorted Array II (this problem, duplicates)
• LC 153 — Find Minimum in Rotated Sorted Array (no duplicates)
• LC 154 — Find Minimum in Rotated Sorted Array II (duplicates, same safe-shrink idea)
• Any "almost sorted" search problem where perturbations (rotations, duplicates) break the standard sorted-half guarantee

Key Takeaway#

When binary search encounters duplicates that make it impossible to determine which half is sorted, the safe move is to shrink the ambiguous boundary by 1 (lo++ or hi--). This preserves correctness — we never discard the target — at the cost of degrading worst-case time to O(n). Always communicate this trade-off proactively in an interview: it signals that you understand not just the algorithm template, but the underlying invariants and their limits.

Key Takeaways#

• LC 81 extends LC 33 (rotated array search) to handle duplicates; it is asked by Google and Microsoft to test understanding of algorithm invariant boundaries.
• When nums[lo] == nums[mid], you cannot determine which half is sorted — the safe escape is lo++ which eliminates one duplicate without discarding the target.
• The algorithm is O(log n) on average and O(n) in the worst case — this trade-off must be stated proactively to interviewers.
• The worst-case O(n) is achieved by inputs like [1,1,1,...,1,0,1] where you must eliminate one 1 at a time.
• LC 154 (Find Minimum in Rotated Array II) uses the symmetric hi-- escape hatch when nums[mid] == nums[hi] — same concept, different comparison side.
• The core LC 33 logic remains unchanged for the non-ambiguous cases: left-sorted check, right-sorted check, target range test.
• Interviewers specifically ask this to check whether you can articulate the invariant breakdown and its cost — not just produce working code.