coding challenges · medium

Search in a Rotated Sorted Array

LeetCode 33 (asked at Arcserve). A sorted array rotated at an unknown pivot is still searchable in O(log n): at each mid, one half ([lo..mid] or [mid..hi]) is fully sorted — detect it with a[lo] <= a[mid], test whether the target lies within that sorted half, and recurse into the correct side. O(1) space. Duplicates make a[lo]==a[mid] ambiguous and can degrade the worst case to O(n).

🔑 Key line

Rotated array search = binary search where one half is always sorted: if target is in the sorted half go there, else the other half. O(log n) time, O(1) space; duplicates can degrade it to O(n).

The code

#include <vector>
#include <cstdio>

// Modified binary search: one half is always sorted; decide which half holds target.
int search(const std::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() {
    std::vector<int> a = {4, 5, 6, 7, 0, 1, 2};
    printf("%d %d\n", search(a, 0), search(a, 3)); // 4 -1
}

What this lesson walks through

01One half is always sorted
02mid = 3 → a[mid] = 7
03mid = 5 → a[mid] = 1
04mid = 4 → found at index 4
05Complexity & the duplicate trap

Rotation breaks the global order but not the local one: at any mid, either [lo..mid] or [mid..hi] is fully sorted. Find which, then decide which side can hold the target.

See it animated — step by step, at your own pace

Unlock the full interactive walkthrough of Search in a Rotated Sorted Array and 100+ animated C++ interview lessons.

Start free →Already a member? Log in →