32.Search in Rotated Sorted Array

MediumBlind 75Binary Search · 5/7

Problem

An ascending array of distinct integers nums has possibly been rotated at an unknown pivot k, so it looks like [nums[k], ..., nums[n-1], nums[0], ..., nums[k-1]]. For example [0,1,2,4,5,6,7] rotated at index 3 becomes [4,5,6,7,0,1,2].

Given the rotated array and an integer target, return the index of target, or -1 if it is not in the array. The algorithm must run in O(log n) time.

Examples

Input:  nums = [4, 5, 6, 7, 0, 1, 2], target = 0
Output: 4
Explanation: 0 sits at index 4, right after the rotation point.

Input:  nums = [4, 5, 6, 7, 0, 1, 2], target = 3
Output: -1
Explanation: 3 is not in the array.

Input:  nums = [1], target = 0
Output: -1

Constraints

1 <= nums.length <= 5000
-10^4 <= nums[i] <= 10^4
All values of nums are unique.
nums is an ascending array that is possibly rotated.
-10^4 <= target <= 10^4

💡 Key Insight

Cut a rotated sorted array at any mid and at least one of the two halves is perfectly sorted. If nums[l] <= nums[mid], the left half [l, mid] is sorted; otherwise the right half [mid, r] is. For the sorted half we can check with two comparisons whether target lies inside its range — if yes, search there; if not, it must be in the other half. That keeps the classic "discard half per step" property.

Brute Force

TimeO(n).SpaceO(1).

Intuition

Ignore the structure and scan every index.

Algorithm

For each i, if nums[i] == target return i.
Return -1.

Visualization

nums = [4, 5, 6, 7, 0, 1, 2], target = 0
4 ✗  5 ✗  6 ✗  7 ✗  0 ✓ → return 4

Code

java

class Solution {
    public int search(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                return i;
            }
        }
        return -1;
    }
}

Complexity

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

Find Pivot, Then Binary Search

TimeO(log n)SpaceO(1).

Intuition

Split the problem in two familiar pieces. First find the index of the minimum (the rotation point) with the technique from Find Minimum in Rotated Sorted Array. The array is then two sorted runs: [0, pivot - 1] holds the large values and [pivot, n - 1] holds the small values. If target <= nums[n - 1] it can only be in the right run; otherwise only in the left run. Run a normal binary search there.

Algorithm

Find pivot (index of the minimum): l = 0, r = n - 1; while l < r, if nums[mid] > nums[r] then l = mid + 1 else r = mid.
If target <= nums[n - 1], search [pivot, n - 1]; else search [0, pivot - 1].
Return the result of that binary search.

Dry Run

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

find pivot: l=0,r=6 mid=3 (7 > 2) → l=4
            l=4,r=6 mid=5 (1 ≤ 2) → r=5
            l=4,r=5 mid=4 (0 ≤ 1) → r=4  → pivot = 4
5 > nums[6] = 2 → search left run [0, 3]
binary search [4,5,6,7] for 5 → index 1

Code

java

class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;

        // 1) index of the minimum element = rotation point
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] > nums[r]) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        int pivot = l;

        // 2) choose the sorted run that can contain target
        if (target <= nums[n - 1]) {
            return binarySearch(nums, pivot, n - 1, target);
        }
        return binarySearch(nums, 0, pivot - 1, target);
    }

    private int binarySearch(int[] nums, int lo, int hi, int target) {
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return -1;
    }
}

Complexity

Time: O(log n) — two binary searches.
Space: O(1).

One-Pass Modified Binary SearchOptimal

TimeO(log n)SpaceO(1).

Intuition

Do it in a single binary search. At each mid, figure out which half is sorted, then test whether target is within that sorted half's bounds:

Left half sorted (nums[l] <= nums[mid]): if nums[l] <= target < nums[mid] go left, else go right.
Right half sorted: if nums[mid] < target <= nums[r] go right, else go left.

Only the sorted half gives a reliable range test, which is why we always reason about it.

Algorithm

l = 0, r = n - 1.
While l <= r:
- mid = l + (r - l) / 2; if nums[mid] == target return mid.
- If nums[l] <= nums[mid]: if nums[l] <= target && target < nums[mid] then r = mid - 1, else l = mid + 1.
- Else: if nums[mid] < target && target <= nums[r] then l = mid + 1, else r = mid - 1.
Return -1.

Dry Run

flowchart TD
    A["nums = [4,5,6,7,0,1,2], target = 0<br/>l=0, r=6"] --> B["mid=3, nums[mid]=7"]
    B --> C{"left half [4..7] sorted<br/>is 0 in [4, 7)?"}
    C -->|"no"| D["l=4, r=6"]
    D --> E["mid=5, nums[mid]=1"]
    E --> F{"left half [0..1] sorted<br/>is 0 in [0, 1)?"}
    F -->|"yes"| G["l=4, r=4"]
    G --> H["mid=4, nums[mid]=0 == target"]
    H --> I["return 4"]

Code

java

class Solution {
    public int search(int[] nums, int target) {
        int l = 0;
        int r = nums.length - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[l] <= nums[mid]) {
                // left half [l, mid] is sorted
                if (nums[l] <= target && target < nums[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else {
                // right half [mid, r] is sorted
                if (nums[mid] < target && target <= nums[r]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        return -1;
    }
}

Complexity

Time: O(log n) — one half is discarded per iteration.
Space: O(1).

Complexity Comparison

Approach	Time	Space
Brute Force	O(n)	O(1)
Find Pivot + Binary Search	O(log n)	O(1)
One-Pass Modified Binary Search	O(log n)	O(1)

Common Pitfalls

Using nums[l] < nums[mid] instead of <= — when l == mid (two-element window) the left "half" is a single sorted element, and the strict check sends you into the wrong branch.
Getting the range bounds' strictness wrong: nums[mid] was already compared, so the tests are nums[l] <= target < nums[mid] and nums[mid] < target <= nums[r].
Testing whether target is in the unsorted half — its endpoints do not bound its contents, so the check is meaningless.
In the pivot approach, forgetting that an unrotated array has pivot = 0, making the left run [0, -1] empty — that case must still work (it does, since target <= nums[n-1] routes to the full array).