Problem statement

An ascending array of distinct values was rotated at an unknown pivot (e.g. [0,1,2,4,5,6,7] → [4,5,6,7,0,1,2]). Given the rotated array nums and a target, return the index of target, or -1 if absent.

Must run in O(log n) time.

Example 1

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Constraints

• 1 <= nums.length <= 30
• -100 <= nums[i], target <= 100
• Distinct values, rotated ascending array.

Hints for Search in Rotated Sorted Array

1. Hint 1

   At any mid, at least one half of the array is properly sorted.

2. Hint 2

   Check whether the target lies inside the sorted half; recurse into the correct side.

How to solve Search in Rotated Sorted Array

A rotated sorted array is two sorted runs joined end to end. Wherever you place mid, at least one side of it is a clean sorted range — and you can tell which by comparing nums[lo] with nums[mid]. Once you know the sorted side, a simple range check says whether the target lives there, and you discard the other half exactly as in ordinary binary search.

Approach

1. Keep an inclusive range and compute mid as usual; return immediately on a hit.
2. If nums[lo] <= nums[mid], the left half is sorted.
3. In that case, if the target lies within [nums[lo], nums[mid]), search left; otherwise search right.
4. Otherwise the right half is sorted: if the target lies within (nums[mid], nums[hi]], search right; otherwise search left.
5. An empty range means the target is absent.

Why it works

The rotation point splits the array into two ascending runs, so mid can fall in at most one of them — the other side is therefore entirely sorted and contiguous. Comparing nums[lo] with nums[mid] identifies which, since a sorted left half must have its first element no greater than its last. On the sorted side, membership is a plain range test; if the target is not there it must be on the other side, so a half is discarded every step and the logarithmic bound survives the rotation.

Complexity

• Time — O(log n)
• Space — O(1)

Pitfalls

• The sortedness test must be nums[lo] <= nums[mid], with the equality — otherwise a two-element range misidentifies which side is sorted.
• The range checks are half-open at the mid end (target < nums[mid], target > nums[mid]) since mid was already tested.
• The array may not be rotated at all; the same logic covers that, with the left half simply always sorted.
• Values are distinct here, which is what makes the comparisons unambiguous — duplicates would break this approach.

Reference solution

Python

from typing import List

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

Java

public static 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;
}

C++

int search(vector<int>& nums, int target) {
    int lo = 0, hi = (int) nums.size() - 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;
}

JavaScript

var search = function(nums, target) {
    let lo = 0, hi = nums.length - 1;
    while (lo <= hi) {
        const mid = (lo + hi) >> 1;
        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;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium