#81

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Search in Rotated Sorted Array II

Determine if a target exists in a rotated sorted array that may contain duplicates using a binary search variation efficiently.

array binary search

Problem Statement

You are given an integer array nums sorted in non-decreasing order, which may contain duplicate values. The array is rotated at an unknown pivot index such that the resulting array starts from nums[k] followed by nums[k+1] to nums[n-1], then nums[0] to nums[k-1]. Your task is to determine if a given integer target exists in this rotated array.

Return true if the target is present in nums, and false otherwise. For example, nums = [2,5,6,0,0,1,2] rotated from a sorted array may have target = 0, which should return true, or target = 3, which should return false. Handle duplicates carefully to maintain efficiency in the binary search over the valid answer space.

Examples

Example 1

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

Output: true

Example details omitted.

Example 2

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

Output: false

Example details omitted.

Constraints

1 <= nums.length <= 5000
-104 <= nums[i] <= 104
nums is guaranteed to be rotated at some pivot.
-104 <= target <= 104

Solution Approach

Modified Binary Search

Perform a standard binary search but handle rotation by comparing mid with left and right boundaries. If duplicates cause ambiguity, increment left or decrement right to reduce the search space.

Handling Duplicate Elements

When nums[left] == nums[mid] == nums[right], we cannot determine which half is sorted, so shrink the boundaries incrementally. This ensures the search space gradually reduces without skipping potential target positions.

Decision Logic for Sorted Halves

After resolving duplicates, identify the sorted half and check if the target lies within it. Adjust pointers accordingly to continue binary search in the promising segment, maintaining O(log n) time in the best scenario and O(n) in the worst-case with many duplicates.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Best-case time complexity is O(log n) when duplicates are minimal, but worst-case can degrade to O(n) due to duplicate values. Space complexity is O(1) as the algorithm operates in-place with only pointers.

What Interviewers Usually Probe

Expect discussion on handling duplicates during binary search in rotated arrays.
Check for clear reasoning about deciding which half is sorted despite rotations.
Notice whether candidate handles worst-case linear scan scenario due to identical elements.

Common Pitfalls or Variants

Common pitfalls

Failing to handle duplicates correctly, leading to infinite loops or missed targets.
Assuming strictly increasing array properties, which breaks with repeated elements.
Overcomplicating the rotation logic instead of shrinking the search space carefully.

Follow-up variants

Search in Rotated Sorted Array without duplicates, which simplifies the binary search logic.
Find the minimum element in a rotated sorted array with duplicates.
Count occurrences of a target in a rotated sorted array allowing duplicates.

FAQ

Why is a simple binary search not enough for Search in Rotated Sorted Array II?

Because duplicates can make it impossible to determine the sorted half, requiring boundary adjustments to maintain correctness.

What is the worst-case time complexity for this problem?

O(n), which occurs when duplicates force the search to reduce boundaries one step at a time.

Can this algorithm work if there are no duplicates?

Yes, it simplifies to standard rotated binary search, achieving O(log n) consistently.

How do I know which half of the array is sorted?

Compare nums[left], nums[mid], and nums[right]; after resolving duplicates, the sorted half can be identified to decide where to continue searching.

Does GhostInterview provide code solutions for Search in Rotated Sorted Array II?

It guides through the stepwise reasoning and edge-case handling rather than giving direct code, ensuring understanding of binary search adjustments.

terminal

Solution

Solution 1: Binary Search

We define the left boundary of the binary search as $l = 0$ and the right boundary as $r = n - 1$, where $n$ is the length of the array.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        n = len(nums)
        l, r = 0, n - 1
        while l < r:
            mid = (l + r) >> 1
            if nums[mid] > nums[r]:
                if nums[l] <= target <= nums[mid]:
                    r = mid
                else:
                    l = mid + 1
            elif nums[mid] < nums[r]:
                if nums[mid] < target <= nums[r]:
                    l = mid + 1
                else:
                    r = mid
            else:
                r -= 1
        return nums[l] == target

Continue Practicing

#74 search a 2d matrix #35 search insert position #34 find first and last position of element in sorted array