Search in Rotated Sorted Array

What does it solve?

Find a target in a sorted array that's been rotated at an unknown pivot (like [4,5,6,7,0,1,2]). A plain binary search breaks because the array isn't globally sorted, but it can still run in O(log N).

Key insight: at any mid, at least one side [lo..mid] or [mid..hi] is fully sorted. Figure out which by comparing endpoints, check whether the target lies within that sorted half's range, and move into it or away from it. Halving each step keeps it O(log N).

The core idea

while lo <= hi:
  mid = (lo+hi)/2
  if a[mid]==target: return mid
  if a[lo] <= a[mid]: # left sorted
    target in [a[lo],a[mid]) ? hi=mid-1 : lo=mid+1
  else: # right sorted
    target in (a[mid],a[hi]] ? lo=mid+1 : hi=mid-1

Complexity

Time complexity

O(log N)

Each step throws away half the array, exactly like ordinary binary search. The rotation only changes which half.

Space complexity

O(1)

Three index variables, no recursion stack in the iterative form.

Examples & edge cases

Live animation — find the sorted half, then narrow

lo mid hi sorted half target found

Array

Current step detail

lo = — mid = — hi = — found = —

Step — of —

a[mid]

—

midpoint value

target

—

searching for

sorted side

—

left / right

answer

—

index

Select an example and press Play to start.

✓ Done

SpeedMedium

Step-by-step table

Step	lo	mid	hi	a[mid]	sorted half	action

C++ implementation

search_rotated.cpp

#include <bits/stdc++.h>
using namespace std;

// Search target in a rotated sorted array, O(log n)
int search(vector<int>& a, int target) {
    int lo = 0, hi = (int)a.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == target) return mid;

        if (a[lo] <= a[mid]) {              // left half is sorted
            if (a[lo] <= target && target < a[mid]) hi = mid - 1;
            else lo = mid + 1;
        } else {                            // right half is sorted
            if (a[mid] < target && target <= a[hi]) lo = mid + 1;
            else hi = mid - 1;
        }
    }
    return -1;
}

int main() {
    vector<int> a = {4,5,6,7,0,1,2};
    cout << search(a, 0) << "\n"; // 4
    return 0;
}

My Notes

📝Notes✅

▼

●Start typing to save...0 chars

Practice this problem