Search in Rotated Sorted Array

Problem Description

An integer array sorted in ascending order was rotated at an unknown pivot. Given the rotated array nums and a target, return the index of target if present, or -1 if not.

All values are unique. You must run in O(log n) time.

Examples

Constraints

• 1 ≤ nums.length ≤ 5000
• -10⁴ ≤ nums[i] ≤ 10⁴
• All values of nums are unique.
• nums is sorted and possibly rotated.
• -10⁴ ≤ target ≤ 10⁴

At Every Step, One of the Two Halves Is Definitely Sorted

Standard binary search works because it can always tell which half to eliminate. In a rotated array, you can still do this by identifying which half is the sorted one. At any mid, either [left, mid] or [mid, right] is a clean sorted range. Check nums[left] <= nums[mid]. If true, the left half is sorted. Check if target falls in that range. If it does, search left. If not, search right. Repeat for the right half.

Solution 1: Find Pivot Then Binary Search

Find the rotation pivot using the approach from “Find Minimum in Rotated Sorted Array,” then decide which sorted subarray to binary search.

class Solution {
    public int search(int[] nums, int target) {
        // find the pivot (index of minimum element)
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right]) left = mid + 1;
            else right = mid;
        }
        int pivot = left;
        // binary search in the half that contains target
        if (target >= nums[pivot] && target <= nums[nums.length - 1]) {
            left = pivot; right = nums.length - 1;
        } else {
            left = 0; right = pivot - 1;
        }
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;
            else if (nums[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return -1;
    }
}

class Solution:
    def search(self, nums: list[int], target: int) -> int:
        # find the pivot (index of minimum element)
        left, right = 0, len(nums) - 1
        while left < right:
            mid = (left + right) // 2
            if nums[mid] > nums[right]: left = mid + 1
            else: right = mid
        pivot = left
        # binary search in the half that contains target
        if target >= nums[pivot] and target <= nums[-1]:
            left, right = pivot, len(nums) - 1
        else:
            left, right = 0, pivot - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target: return mid
            elif nums[mid] < target: left = mid + 1
            else: right = mid - 1
        return -1

#include <vector>

class Solution {
public:
    int search(std::vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right]) left = mid + 1;
            else right = mid;
        }
        int pivot = left;
        if (target >= nums[pivot] && target <= nums.back())
            left = pivot, right = nums.size() - 1;
        else
            left = 0, right = pivot - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;
            else if (nums[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return -1;
    }
};

Complexity Analysis:

• Time Complexity: O(log n). Two binary searches.
• Space Complexity: O(1).

Where it breaks: two separate passes. The single-pass approach below is cleaner and equally fast.

Solution 2: Single-Pass Binary Search with Half Identification

At each step, determine which half is sorted. If target is in the sorted half, search there. Otherwise, search the other half.

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

            if (nums[left] <= nums[mid]) {
                // left half is sorted; check if target belongs there
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                // right half is sorted; check if target belongs there
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
}

class Solution:
    def search(self, nums: list[int], target: int) -> int:
        left, right = 0, len(nums) - 1

        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid

            if nums[left] <= nums[mid]:
                # left half is sorted; check if target belongs there
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                # right half is sorted; check if target belongs there
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1

        return -1

#include <vector>

class Solution {
public:
    int search(std::vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;

            if (nums[left] <= nums[mid]) {
                // left half is sorted; check if target belongs there
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                // right half is sorted; check if target belongs there
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
};

Complexity Analysis:

• Time Complexity: O(log n). One binary search pass.
• Space Complexity: O(1).

Where it breaks: if the array has duplicates, nums[left] == nums[mid] becomes possible and you can’t determine which half is sorted. The safe fallback is left++, which degrades worst case to O(n).

Common Mistakes

• Using strict less-than in the sorted half check. The condition for checking if target is in the left sorted half must be nums[left] <= target && target < nums[mid], not nums[left] < target. Missing the = on the left loses the case where target == nums[left].
• Forgetting nums[left] <= nums[mid] can be true when the array is not rotated. In a fully sorted array, this condition is always true, and the logic still works correctly.
• Confusing this problem with Find Minimum. Here you use left <= right as the loop condition and check for equality first. In Find Minimum you use left < right and don’t check equality explicitly.

Frequently Asked Questions

Why does nums[left] <= nums[mid] tell you the left half is sorted? In a rotated sorted array with unique elements, if the leftmost element is less than or equal to mid, there’s no break point between them, so that subarray is sorted. The break point must be in the right half.

What if the target equals nums[left] or nums[right]? The check nums[mid] == target at the top catches it when mid lands on it. Otherwise, the boundary conditions in the sorted half checks handle it through the standard binary search narrowing.

How does this differ from Find Minimum in Rotated Sorted Array? Find Minimum only needs to find the break point; it always converges to left == right using strict less-than loop condition. This problem needs to search for a target value, so it uses left <= right and checks equality explicitly.

← All Problems