Skip to main content
CodePeetCodePeet
CodePeet 250

Search in Rotated Sorted Array

MEDIUMProblemSolveExternal Links

Description

You are given an integer array nums that was originally sorted in ascending order with all distinct values. Before being passed to you, this array was rotated at some unknown pivot index k (where 1 ≤ k < nums.length). After rotation, the array looks like:

[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]

For example, the sorted array [0, 1, 2, 4, 5, 6, 7] might be rotated by 3 positions to become [4, 5, 6, 7, 0, 1, 2].

Given this rotated array and a target value, return the index of target in the array, or -1 if it is not present.

You must design an algorithm that runs in O(log n) time complexity.

Examples

Example 1

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

Output: 4

Explanation: The original sorted array [0, 1, 2, 4, 5, 6, 7] was rotated by 4 positions. The target value 0 is found at index 4 in the rotated array.

Example 2

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

Output: -1

Explanation: The value 3 does not exist in the array at all. The array contains [4, 5, 6, 7, 0, 1, 2], and none of these values equal 3, so we return -1.

Example 3

Input: nums = [1], target = 0

Output: -1

Explanation: The array has only one element (1), and the target is 0. Since 1 ≠ 0, the target is not found and we return -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

Editorial

Brute Force

Intuition

The most straightforward approach is to ignore the fact that the array was ever sorted or rotated and simply scan every element one by one. If we find the target, we return its index. If we reach the end without finding it, we return -1.

This is the approach you would use if you had no knowledge about the array's structure at all — just look at everything sequentially until you either find what you need or confirm it is absent. It is like searching for a specific book on a shelf by checking each book from left to right, regardless of any alphabetical ordering.

Step-by-Step Explanation

Let's trace through with nums = [4, 5, 6, 7, 0, 1, 2], target = 0:

Step 1: Start at index 0. nums[0] = 4. Is 4 == 0? No. Move to next index.

Step 2: Index 1. nums[1] = 5. Is 5 == 0? No. Move on.

Step 3: Index 2. nums[2] = 6. Is 6 == 0? No. Move on.

Step 4: Index 3. nums[3] = 7. Is 7 == 0? No. Move on.

Step 5: Index 4. nums[4] = 0. Is 0 == 0? Yes! We found the target.

Step 6: Return index 4.

Linear Search — Scanning Every Element — Watch how linear search checks each element sequentially, making no assumptions about the array's structure, until it finds the target or exhausts all elements.

Algorithm

  1. For each index i from 0 to n - 1:
    • If nums[i] equals the target, return i
  2. If the loop completes without finding the target, return -1

Code

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;
    }
};
class Solution:
    def search(self, nums: list[int], target: int) -> int:
        for i in range(len(nums)):
            if nums[i] == target:
                return i
        return -1
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 Analysis

Time Complexity: O(n)

In the worst case, we scan the entire array of n elements before finding the target (or confirming its absence). Each element requires O(1) work (a single comparison), so total time is O(n).

Space Complexity: O(1)

We only use a single loop variable i. No additional data structures are created, so space usage is constant.

Why This Approach Is Not Efficient

The brute force takes O(n) time, but the problem explicitly requires O(log n). With n up to 5000, the linear search itself is fast enough to pass, but it fails the algorithmic requirement.

More importantly, the linear search wastes the structural information we are given. The array was sorted before rotation, which means it still has significant structure: it consists of two sorted segments. A rotated sorted array like [4, 5, 6, 7, 0, 1, 2] has a left sorted portion [4, 5, 6, 7] and a right sorted portion [0, 1, 2].

Whenever an array (or part of it) is sorted, we can use binary search to eliminate half the elements at each step, achieving O(log n) time. The challenge is adapting binary search to handle the rotation point where the two sorted halves meet.

Key insight: At any midpoint in a rotated sorted array, at least one of the two halves (left or right of mid) is guaranteed to be sorted. We can determine which half is sorted, check if the target falls within that sorted range, and decide which half to search — effectively performing binary search despite the rotation.

Optimal Approach - Modified Binary Search

Intuition

The key observation that makes this problem solvable in O(log n) is that a rotated sorted array is actually composed of two sorted subarrays. When you pick any midpoint, at least one half of the array (left or right of mid) will always be properly sorted.

Here is the reasoning: in a rotated sorted array, the rotation creates exactly one "break point" where a larger number is immediately followed by a smaller number. When you choose a midpoint, this break point can only be in one half — meaning the other half is a clean, uninterrupted sorted sequence.

Once you identify which half is sorted, you can easily determine whether the target lies within that sorted half by checking if the target falls between the half's minimum and maximum values. If it does, search that half. If it does not, search the other half. Either way, you eliminate half the search space at each step — exactly what binary search does.

Think of it like searching for a house number on a circular street. The street numbers go 1, 2, 3, ..., 100 around the circle. If you start at position 40, you can see that numbers increase to 100 on your right and decrease to 1 on your left. If you are looking for house 75, you know it is somewhere in the increasing direction — you do not need to check the other direction at all.

Step-by-Step Explanation

Let's trace with nums = [4, 5, 6, 7, 0, 1, 2], target = 0:

Step 1: Initialize lo = 0, hi = 6.

Step 2: Compute mid = (0 + 6) / 2 = 3. nums[mid] = nums[3] = 7. Is 7 == 0? No.

Step 3: Determine which half is sorted.

  • Check: nums[lo] = nums[0] = 4 ≤ nums[mid] = 7? Yes → the left half [4, 5, 6, 7] is sorted.

Step 4: Does the target lie in the sorted left half?

  • Check: target ≥ nums[lo] (0 ≥ 4)? No. → Target 0 does NOT fall in [4, 7]. So search the right half.
  • Update: lo = mid + 1 = 4.

Step 5: Now lo = 4, hi = 6. Compute mid = (4 + 6) / 2 = 5. nums[mid] = nums[5] = 1. Is 1 == 0? No.

Step 6: Determine which half is sorted.

  • Check: nums[lo] = nums[4] = 0 ≤ nums[mid] = 1? Yes → the left half [0, 1] is sorted.

Step 7: Does the target lie in this sorted left half?

  • Check: target ≥ nums[lo] (0 ≥ 0)? Yes. target < nums[mid] (0 < 1)? Yes. → Target is in [0, 1]. Search this half.
  • Update: hi = mid - 1 = 4.

Step 8: Now lo = 4, hi = 4. Compute mid = 4. nums[4] = 0. Is 0 == 0? Yes! Found it.

Step 9: Return 4.

Modified Binary Search — Identifying the Sorted Half — At each step, we identify which half of the array is sorted, check if the target lies within that sorted range, and eliminate the other half. Watch how we narrow the search space logarithmically.

Algorithm

  1. Initialize two pointers: lo = 0, hi = n - 1
  2. While lo ≤ hi:
    a. Compute mid = lo + (hi - lo) / 2
    b. If nums[mid] == target, return mid
    c. Determine which half is sorted:
    • If nums[lo] ≤ nums[mid], the left half is sorted:
      • If target ≥ nums[lo] AND target < nums[mid], the target is in the left half → set hi = mid - 1
      • Otherwise, the target is in the right half → set lo = mid + 1
    • Else, the right half is sorted:
      • If target > nums[mid] AND target ≤ nums[hi], the target is in the right half → set lo = mid + 1
      • Otherwise, the target is in the left half → set hi = mid - 1
  3. If the loop ends without finding the target, return -1

Code

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int lo = 0, hi = nums.size() - 1;
        
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            
            if (nums[mid] == target) {
                return mid;
            }
            
            // Left half is sorted
            if (nums[lo] <= nums[mid]) {
                if (target >= nums[lo] && target < nums[mid]) {
                    hi = mid - 1;
                } else {
                    lo = mid + 1;
                }
            }
            // Right half is sorted
            else {
                if (target > nums[mid] && target <= nums[hi]) {
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
        }
        
        return -1;
    }
};
class Solution:
    def search(self, nums: list[int], target: int) -> int:
        lo, hi = 0, len(nums) - 1
        
        while lo <= hi:
            mid = lo + (hi - lo) // 2
            
            if nums[mid] == target:
                return mid
            
            # Left half is sorted
            if nums[lo] <= nums[mid]:
                if nums[lo] <= target < nums[mid]:
                    hi = mid - 1
                else:
                    lo = mid + 1
            # Right half is sorted
            else:
                if nums[mid] < target <= nums[hi]:
                    lo = mid + 1
                else:
                    hi = mid - 1
        
        return -1
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;
            }
            
            // Left half is sorted
            if (nums[lo] <= nums[mid]) {
                if (target >= nums[lo] && target < nums[mid]) {
                    hi = mid - 1;
                } else {
                    lo = mid + 1;
                }
            }
            // Right half is sorted
            else {
                if (target > nums[mid] && target <= nums[hi]) {
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
        }
        
        return -1;
    }
}

Complexity Analysis

Time Complexity: O(log n)

At each iteration of the while loop, we eliminate roughly half of the remaining search space by moving either lo or hi to exclude one side of the midpoint. Starting with n elements, the search space shrinks as: n → n/2 → n/4 → ... → 1. This halving process takes at most log₂(n) iterations. Each iteration performs O(1) work (a few comparisons and one pointer update), so total time is O(log n).

Space Complexity: O(1)

We only use three integer variables (lo, hi, mid) regardless of the input size. No recursion is used, so there is no call stack overhead. The space is constant.