mediumDSA

How do you search in a rotated sorted array?

Q: How do you search in a rotated sorted array?

**Intuition.** A sorted array rotated at some pivot still has the property that, for any midpoint, **at least one half is fully sorted**. Run binary search; at each step figure out which half is sorted, check whether the target lies within that sorted half's range, and discard the other half. [4,5,6,7,0,1,2] target 0 — left half sorted, right not 4 <rect x="90" y="44" width="56" height="38" rx="5" fill="#3b82f6" fill-opacity="0.

891 views

Understand the problem

Explain modified binary search.

binary-searcharrays

Attempt it yourself

Sketch your approach before reading the solution — that's what interviews test.

Stuck? AI Nudge Available

Get a conceptual hint to guide your logic without spoiling the final implementation.

Study the solution

The solution is waiting

Give it an honest attempt first — then compare your thinking with the full walkthrough.

Read the code

Binary search on a rotated array

Run Playground

def search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:                 # left half sorted
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:                                     # right half sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1


# --- demo ---
print(search([4, 5, 6, 7, 0, 1, 2], 0))   # 4
print(search([4, 5, 6, 7, 0, 1, 2], 3))   # -1

Join the discussion

Discussion (0)

No responses yet. Be the first to share what you think.

How do you remove the nth node from the end of a linked list?

How do you rotate an array by k positions?