{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Search in Rotated Sorted Array – Solution & Complexity

Interview solutions
/
Search in Rotated Sorted Array

Solution Walkthrough

  1. Step 1: Understanding the Problem

    • The array was sorted ascending, then rotated at some unknown pivot (e.g. [0,1,2,4,5,6,7] rotated at index 3 becomes [4,5,6,7,0,1,2]).
    • You need to find target's index in O(log n) — a plain linear scan is O(n) and defeats the point of the problem.
    • Key insight: even though the whole array isn't sorted, at least one of the two halves around any midpoint always is sorted. That's enough to still binary search.

  2. Step 2: Modified Binary Search

    • Keep lo/hi pointers like standard binary search. At each step compute mid.
    • Determine which half is sorted by comparing nums[lo] and nums[mid]: if nums[lo] <= nums[mid], the left half [lo..mid] is sorted; otherwise the right half [mid..hi] is sorted.
    • Once you know which half is sorted, checking whether target lies within that half's value range is a simple comparison. If it does, search that half; otherwise, search the other half.

  3. Step 3: Working Through the Branches

    • If nums[mid] == target, return mid immediately.
    • If left half [lo..mid] is sorted: target is in it exactly when nums[lo] <= target < nums[mid], so narrow hi = mid - 1; otherwise narrow lo = mid + 1.
    • If the right half [mid..hi] is sorted instead: target is in it exactly when nums[mid] < target <= nums[hi], so narrow lo = mid + 1; otherwise narrow hi = mid - 1.
    • Loop while lo <= hi; if the loop ends without finding target, return -1.

  4. Step 4: Final Solution (all languages)

    This still runs in O(log n) time and O(1) space — the halving still happens every iteration, just with an extra comparison to figure out which half is sorted.

    def search(nums: list[int], target: int) -> int:
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

  5. Step 5: Common mistakes & interviewer follow-ups

    • Using nums[lo] < nums[mid] instead of <= to detect the sorted half — with only 1-2 elements in a half, lo == mid and the strict inequality misclassifies it as unsorted.
    • Off-by-one errors in the range checks (< vs <= at the boundaries) — easy to skip or double-count the boundary element.
    • Follow-ups: how does the approach change if the array can contain duplicates (values equal to nums[lo] making it ambiguous which half is sorted — worst case degrades to O(n))? How would you find the rotation pivot index itself?
Learn the Binary Search pattern: recognition cues, invariant, and ordered practice →

FAQ

See also

Practice Search in Rotated Sorted Array online (run code in the browser)Binary Search solution (easy)Find Minimum in Rotated Sorted Array solution (medium)Koko Eating Bananas solution (medium)Longest Increasing Subsequence solution (hard)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?