Search in Rotated Sorted Array

MediumModified Binary SearchBlind 75MidOpen on LeetCodeUpdated Sep 21, 2026

You're given an array nums of distinct integers that was sorted in ascending order and then possibly rotated at an unknown index, so [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]. Given an integer target, return the index where it appears in nums, or -1 if it is not present. Your solution must run in O(log n) time.

Examples

nums = [4,5,6,7,0,1,2], target = 0 returns 4

0 is at index 4, where the original first value landed.

The original [0,1,2,4,5,6,7] was rotated so it now starts at 4. The target 0 sits at index 4, right after the drop from 7.

nums = [4,5,6,7,0,1,2], target = 3 returns -1

No element equals 3, so the answer is -1.

nums = [3,1], target = 1 returns 1

This is [1,3] rotated by one position. The target 1 is at index 1.

Constraints

1 <= nums.length <= 5000
All values unique.

Hints

Hint 1

Even after rotation, at least one half of the array around the midpoint is still sorted, can you exploit that?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

Keep a range [lo, hi] and check the middle. If nums[mid] is the target, return mid. Otherwise one side of mid is fully sorted: if nums[lo] <= nums[mid] it is the left side, so go left only when nums[lo] <= target < nums[mid]; otherwise the right side is sorted, so go right only when nums[mid] < target <= nums[hi]. Each step discards half the range. O(log n) time, O(1) space.

Time

O(log n)

Space

O(1)

Pitfall

Testing nums[lo] < nums[mid] instead of <= to spot a sorted left side. When lo == mid the one-element left side is sorted, and the strict test sends nums = [3,1], target = 1 the wrong way and returns -1.

Solutions

class Solution {
    public int search(int[] nums, int target) {
        int lo = 0, hi = nums.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] == target) return mid;
            if (nums[lo] <= nums[mid]) {
                if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
                else lo = mid + 1;
            } else {
                if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
                else hi = mid - 1;
            }
        }
        return -1;
    }
}

class Solution:
    def search(self, nums, 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