What is the time and space complexity of Search in Rotated Sorted Array II?

Time complexity: O(log n) average, O(n) worst with all duplicates. Space complexity: O(1).

Search in Rotated Sorted Array II

Med

Concept

Code

Loading editor...

Tap Analyze to see visualization

Click Analyze to visualize

See step-by-step execution, variables, and output

Variables

Run code to see variables

Output

Console output will appear here

Press Space to start•← → to step•? all shortcuts

Solution Guide: Search in Rotated Sorted Array II

Approach

Use the same rotated-search logic as LeetCode 33, but when left, mid, and right are equal, drop both boundaries by one because duplicates remove the sorted-half decision.

Complexity Analysis

Time: O(log n) average, O(n) worst with all duplicates
Space: O(1)

Pattern

Binary Search (Rotated Array)

Why It Works

When all three values are equal, duplicates hide ordering information so we shrink the range. Otherwise one half is sortable and can decide if target is inside it.

Updated Feb 2026