Search in Rotated Sorted Array

Med
Concept
Code
Loading editor...
Tap Analyze to see visualization
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

Approach

At each step, identify which half around mid is properly sorted by comparing endpoints. If the target falls within the sorted half, search there. Otherwise, search the other half. One half is always sorted in a rotated array.

Complexity Analysis

Time
O(log n)
Space
O(1)

Pattern

Binary Search (Rotated Array)

Why It Works

After rotation, at least one half around mid is always sorted. Checking which half is sorted lets us determine if the target falls in that range or the other half.

Updated Feb 2026