Code Logo

Search in Rotated Sorted Array

Published at24 Jul 2026
Created by
Medium 0 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
Recommendation Algorithm Flow for Search in Rotated Sorted Array

Solution Approach

Modified binary search: determine which half is sorted, then check if target is in that half.

function solution(nums, target) {
  var lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    var mid = Math.floor((lo + hi) / 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;
}

Time O(log n), Space 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;
    }
}