Search in Rotated Sorted Array

A sorted array has been rotated at an unknown pivot. Find the index of a target value in O(log n), or -1 if absent.

MediumMust DoBinary SearchRotated ArrayLeetCode

Why solve this?

It teaches the key extension to binary search: the array isn't fully sorted, but one of the two halves around any midpoint always is.

Pattern recognition

Whenever an array is 'sorted but rotated', binary search still applies — at every midpoint, exactly one half is guaranteed sorted, and you decide which half to search using that half's bounds.

Prerequisites

Binary Search

Hints

The array as a whole isn't sorted, but is there a smaller sorted piece around any midpoint?
At each step, at least one of the two halves (left of mid, or right of mid) is guaranteed sorted — figure out which.
Once you know which half is sorted, checking if the target lies in that half's range is a plain comparison.

Approach

At each step, compare `nums[mid]` against `nums[lo]` to determine which half is sorted. If the left half (`nums[lo..mid]`) is sorted, check whether `target` falls within `[nums[lo], nums[mid])`; if so search left, otherwise search right. If the right half is sorted instead, apply the symmetric check. This keeps the search space halving every step, just like ordinary binary search.

Java solution

Solution.java

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]) {
                // Left half is sorted.
                if (nums[lo] <= target && target < nums[mid]) {
                    hi = mid - 1;
                } else {
                    lo = mid + 1;
                }
            } else {
                // Right half is sorted.
                if (nums[mid] < target && target <= nums[hi]) {
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
        }
        return -1;
    }
}

Time: O(log n)Space: O(1)