Code Logo

Search in Rotated Sorted Array

Published at24 Jul 2026
Created by
Medium 1 views
Like0

There is an integer array sorted in ascending order that has been rotated at an unknown pivot. For example, [4,5,6,7,0,1,2] was originally [0,1,2,4,5,6,7]. Given this rotated array and a target value, return the index of the target if it exists, or -1 if it does not. The algorithm must run in O(log n) time.

A standard binary search relies on a fully sorted array to decide which half to recurse into. In a rotated array, at least one half is always fully sorted. By comparing the middle element with the left boundary, we can determine which half is sorted: if nums[left] <= nums[mid], the left half is sorted; otherwise, the right half is sorted. Then check if the target lies within the sorted half and narrow the search accordingly.

This modified binary search preserves the O(log n) time complexity while handling the rotation. The key insight is that even though the whole array is not sorted, one side of the midpoint always is. The pivot point creates two contiguous sorted segments, and the midpoint always falls into one of them.

Edge cases include a single-element array, an array rotated n times (back to original order), a target that does not exist, and duplicate values (though LeetCode's version guarantees distinct values).

Example Input & Output

Example 1
Input
[4,5,6,7,0,1,2], 0
Output
4
Explanation

Target 0 is at index 4 in rotated array.

Example 2
Input
[1,3], 3
Output
1
Explanation

Target 3 at index 1.

Example 3
Input
[1], 0
Output
-1
Explanation

Single element, not the target.

Example 4
Input
[3,1], 1
Output
1
Explanation

Rotated at pivot, target 1 at index 1.

Example 5
Input
[4,5,6,7,0,1,2], 3
Output
-1
Explanation

Target 3 does not exist.

Algorithm Flow

Recommendation Algorithm Flow for Search in Rotated Sorted Array

Solution Approach

Search for a target in a rotated sorted array using a modified binary search. A rotated array has a pivot point where the order resets. Determine which half is sorted by comparing nums[left] with nums[mid]. If the left half is sorted and the target lies within its range, search left; otherwise search right. If the right half is sorted and the target lies within its range, search right; otherwise search left.

function search(nums, target) {
  var left = 0, right = nums.length - 1;
  while (left <= right) {
    var mid = Math.floor((left + right) / 2);
    if (nums[mid] === target) return mid;
    if (nums[left] <= nums[mid]) {
      if (target >= nums[left] && target < nums[mid]) right = mid - 1;
      else left = mid + 1;
    } else {
      if (target > nums[mid] && target <= nums[right]) left = mid + 1;
      else right = mid - 1;
    }
  }
  return -1;
}

The key insight is that at each step, at least one half of the array is normally sorted. By checking which half is sorted and whether the target falls in its range, we can decide which half to discard. This preserves O(log n) performance despite the rotation.

Time complexity is O(log n), space complexity is O(1).

Best Answers

java
class Solution {
    public int solution(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]) {
                if (target >= nums[lo] && target < nums[mid]) hi = mid - 1;
                else lo = mid + 1;
            } else {
                if (target > nums[mid] && target <= nums[hi]) lo = mid + 1;
                else hi = mid - 1;
            }
        }
        return -1;
    }
}