Search in Rotated Sorted Array

medium
Binary SearchArrayBinary Search

Given an integer array nums sorted in ascending order with distinct values that has been rotated at an unknown pivot index, and an integer target, return the index of target in nums, or -1 if it is not present. You must write an algorithm with O(log n) runtime complexity.

For example, [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2] after rotation at pivot index 3.

Examples

Example 1

  • Input: nums = [4,5,6,7,0,1,2], target = 0
  • Output: 4
  • Explanation: The target 0 is found at index 4.

Example 2

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

Example 3

  • 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 has been rotated.
  • -10^4 <= target <= 10^4

Approaches

2 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Linear Search

Intuition

The simplest approach is to iterate through the array and check each element. Although this does not take advantage of the sorted property and runs in linear time, it is straightforward and always correct. For small arrays this may be sufficient, but it does not meet the O(log n) requirement for larger inputs.

Algorithm

  1. Iterate through each element of the array from index 0 to n - 1.
  2. If the current element equals the target, return the current index.
  3. If the loop completes without finding the target, return -1.
TimeO(n)SpaceO(1)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int search(vector<int>& nums, int target) {
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == target) {
                return i;
            }
        }
        return -1;
    }
};
Java 21
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;
    }
}
Python 3.12
def search(nums: list[int], target: int) -> int:
    for i in range(len(nums)):
        if nums[i] == target:
            return i
    return -1
Go 1.26
func search(nums []int, target int) int {
    for i, num := range nums {
        if num == target {
            return i
        }
    }
    return -1
}
Approach 2

Modified Binary Search

Intuition

Even though the array is rotated, at least one half of the array (split at mid) is always sorted. We can determine which half is sorted by comparing nums[left] with nums[mid]. If the left half is sorted and the target falls within that range, we search the left half; otherwise, we search the right half. This lets us eliminate half the search space each iteration, achieving O(log n) time.

Algorithm

  1. Initialize left = 0 and right = n - 1.
  2. While left <= right, compute mid = left + (right - left) / 2.
  3. If nums[mid] equals the target, return mid.
  4. Determine which half is sorted: if nums[left] <= nums[mid], the left half is sorted.
  5. If the left half is sorted and target is in the range [nums[left], nums[mid]), search left by setting right = mid - 1. Otherwise, search right by setting left = mid + 1.
  6. If the right half is sorted and target is in the range (nums[mid], nums[right]], search right by setting left = mid + 1. Otherwise, search left by setting right = mid - 1.
  7. If the loop ends without finding the target, return -1.
TimeO(log n)SpaceO(1)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int search(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]) {
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }

        return -1;
    }
};
Java 21
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]) {
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }

        return -1;
    }
}
Python 3.12
def search(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2

        if nums[mid] == target:
            return mid

        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1

    return -1
Go 1.26
func search(nums []int, target int) int {
    left, right := 0, len(nums)-1

    for left <= right {
        mid := left + (right-left)/2

        if nums[mid] == target {
            return mid
        }

        if nums[left] <= nums[mid] {
            if nums[left] <= target && target < nums[mid] {
                right = mid - 1
            } else {
                left = mid + 1
            }
        } else {
            if nums[mid] < target && target <= nums[right] {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
    }

    return -1
}

Frequently asked questions

What is the optimal time complexity of Search in Rotated Sorted Array?

The most efficient approach in this guide ("Modified Binary Search") runs in O(log n) time and uses O(1) extra space. Earlier brute-force approaches are slower; see all 2 approaches above for the full progression.

What pattern does Search in Rotated Sorted Array use?

Search in Rotated Sorted Array is a medium-level Binary Search problem involving Array, Binary Search. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Search in Rotated Sorted Array be solved without extra space?

The most space-efficient approach in this guide uses O(1) extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(1), while the optimized version uses O(1).

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Related Problems

Find Minimum in Rotated Sorted Array

Original problem: leetcode.com

Loading editor...
Input
nums=
[4,5,6,7,0,1,2]
target=
0
Expected Output
4