Search in Rotated Sorted Array

Difficulty: Medium

Problem

You are given an integer array nums whose values are distinct and were originally in ascending order, but the array may have been rotated: a block from the front was moved to the back at some unknown point. For instance, [10,20,30,40,50] could turn into [40,50,10,20,30]. Given the array in its current state and an integer target, return the index where target sits, or -1 if it is not present. Your algorithm must run in O(log n) time.

Example

Input: nums = [6, 7, 8, 1, 2, 3, 4, 5], target = 3
Output: 5
Explanation: 3 sits at index 5 in the rotated array.

Brute-force approach

Scan the entire array linearly to find the target.

Steps

  1. For each index i from 0 to n-1:
  2. If nums[i] == target, return i
  3. Return -1

Time complexity: O(n) · Space complexity: O(1)

Trade-offs

  • Doesn't use the rotated-sorted structure at all
  • O(n) instead of O(log n)
  • Wastes the near-sorted property of the array

Optimal approach

Key insight: In a rotated sorted array, at least one half (left or right of mid) is always fully sorted. Check if the target lies in the sorted half's range. If yes, search there. If no, search the other half.

Modified binary search: at each step, determine which half is sorted, then check if the target falls within that sorted range to decide which half to search.

Steps

  1. Set left = 0, right = n - 1
  2. While left <= right:
  3. mid = (left + right) / 2. If nums[mid] == target, return mid
  4. If nums[left] <= nums[mid] (left half sorted):
  5. If target in [nums[left], nums[mid]): right = mid - 1
  6. Else: left = mid + 1
  7. Else (right half sorted):
  8. If target in (nums[mid], nums[right]]: left = mid + 1
  9. Else: right = mid - 1
  10. Return -1

Time complexity: O(log n) · Space complexity: O(1)

Pseudocode

function search(nums, target):
    left = 0, right = len(nums) - 1
    while left <= right:
        mid = left + (right - left) / 2
        if nums[mid] == target: return mid
        if nums[left] <= nums[mid]:  // left half is sorted
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:  // right half is sorted
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1

Hints

  • At least one half of the array (left or right of mid) is always sorted
  • Determine which half is sorted, then check if the target lies in that sorted range
  • If the target is in the sorted half, search there; otherwise search the other half

Complexity questions

What is the time complexity of linear search on a rotated sorted array?

O(n). Linear search checks each element, O(n), ignoring all structure.

What is the time complexity of the modified binary search?

O(log n). Each step eliminates half the array by identifying the sorted half. O(log n) total.

What is the space complexity?

O(1). Only three pointer variables: O(1).

Check your understanding of Search in Rotated Sorted Array

What does 'rotated sorted array' mean?

A sorted array where some elements were moved from the beginning to the end (or vice versa). A rotated sorted array was originally sorted, then some prefix was moved to the end. Example: [1,2,3,4,5] rotated by 3 becomes [4,5,1,2,3]. It has two sorted halves.

In [4, 5, 6, 7, 0, 1, 2], which halves are sorted?

Both [4,5,6,7] and [0,1,2] are individually sorted. A rotated sorted array always has two sorted sub-arrays. Here: [4,5,6,7] is sorted and [0,1,2] is sorted. The 'break point' is between 7 and 0.

Why can't we use standard binary search directly?

The array is not fully sorted: standard binary search assumes complete sorted order. Standard binary search assumes the entire array is sorted. In a rotated array, the global order is broken at the pivot. We need a modified binary search that identifies which half is sorted before deciding where to search.

Related problems

Keep practising