Search in a Rotated Sorted Array — Modified Binary Search

What does it solve?

An array that was sorted ascending has been rotated at some unknown pivot (e.g. [0,1,2,4,5,6,7] → [4,5,6,7,0,1,2]). Find the index of a target value — or return -1 — in O(log n), not O(n).

Key insight: even though the whole array isn't sorted, at least one half of every window always is. Figure out which half, then decide which side the target could be in.

The core idea

// at every window [lo..hi]:
mid = (lo + hi) / 2
if a[lo] <= a[mid]: // left half sorted
target in [a[lo], a[mid]) ? go left : go right
else: // right half sorted
target in (a[mid], a[hi]] ? go right : go left

Complexity

Time complexity

O(log n)

Still a binary search — the window halves every step, rotation or not.

Space complexity

O(1)

Just two pointers, lo and hi — no extra data structures.

Examples & edge cases

Live animation

🎯 Target: —

mid sorted half other half out of window found

Step — of —

Window [lo..hi]

—

mid

—

Sorted half

—

Step

—

Select an example and press Play to start.

✓ Complete

Speed Medium

Step-by-step table

Step	Window	mid	a[mid]	Sorted half	Decision

C++ implementation

search_rotated.cpp

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

int search(vector<int>& nums, int target) {
    int lo = 0, hi = nums.size() - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] == target) return mid;

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

int main() {
    vector<int> nums = {4,5,6,7,0,1,2};
    int target = 0;

    cout << "Index: " << search(nums, target) << "\n";
    return 0;
}

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars