Search in Rotated Sorted Array

mediumBinary Search18 stepsJava · Python · C++

Find target in a rotated sorted array in O(log n). At least one half around mid is always sorted. Check whether the target lies inside that sorted half; if so, search there, otherwise search the other half.

▶ Watch the animated trace

Traced input: nums = [4, 5, 6, 7, 0, 1, 2], target = 0 → 4. Original problem: neetcode.io/problems/find-target-in-rotated-sorted-array

Complexity

BestO(1)

AverageO(log n)

WorstO(log n)

SpaceO(1)

Values are distinct.

Key idea

If nums[lo] <= nums[mid], the left half [lo, mid] is sorted; otherwise the right half is.
For the sorted half you can test target against its two ends.
If the target is inside that range, keep that half; otherwise keep the other.

Common mistakes

Using < instead of <= in nums[lo] <= nums[mid] breaks when lo == mid.
Getting the inclusive/exclusive bounds wrong in the range checks.
Finding the pivot first and then searching works, but is two passes.

Solution

Java

int searchRotated(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;
}

Python

def searchRotated(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

C++

int searchRotated(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;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Target missing No half's range contains 3.	`nums = [4, 5, 6, 7, 0, 1, 2], target = 3`	`-1`
Single element One check.	`nums = [1], target = 0`	`-1`
Not rotated The left half is always sorted.	`nums = [1, 2, 3, 4, 5], target = 4`	`3`
Two elements, rotated `lo == mid` here, which is why the check uses `<=`.	`nums = [3, 1], target = 1`	`1`