AlgoMaster Logo

Search in Rotated Sorted Array

medium5 min readUpdated June 23, 2026

Understanding the Problem

We have a sorted array that's been rotated at some unknown pivot. For example, [0, 1, 2, 4, 5, 6, 7] rotated at index 3 becomes [4, 5, 6, 7, 0, 1, 2]. The rotation breaks the global sorted order, but it creates two sorted halves: [4, 5, 6, 7] and [0, 1, 2]. We need to find a given target in this array, and we need to do it in O(log n) time.

Even after rotation, at least one half of the array (when split at the midpoint) is always sorted. If the left half is sorted, we can check whether the target falls within its range. If it does, we search left. If not, we search right. The same logic applies when the right half is sorted. This eliminates half the array at each step, like standard binary search.

Key Constraints:

  • The problem explicitly requires O(log n) runtime, which rules out a linear scan and points to binary search.
  • All values of nums are unique. Without duplicates, comparing nums[left] with nums[mid] always tells us which half is sorted (a duplicate-laden array can make that comparison ambiguous).
  • Values stay within the standard 32-bit integer range, so there are no overflow concerns even when computing the midpoint.

Approach 1: Linear Scan

Intuition

Walk through the array and check every element. If we find the target, return its index. If we reach the end, return -1.

This ignores the sorted and rotated structure entirely, so it works on any array, not only rotated sorted ones. It runs in O(n) and violates the problem's O(log n) requirement, but it establishes a baseline for the optimization that follows.

Algorithm

  1. Iterate through the array with index i from 0 to n - 1.
  2. If nums[i] == target, return i.
  3. If the loop finishes without finding the target, return -1.

Example Walkthrough

1Start scan: i=0, looking for target=0
0
4
i
1
5
2
6
3
7
4
0
5
1
6
2
1/4

Code

The linear scan works but doesn't meet the O(log n) requirement. Since the array has two sorted halves, we can use a modified binary search to eliminate half the search space at each step.

Approach 2: Modified Binary Search

Intuition

Standard binary search works on fully sorted arrays. A rotated sorted array is not fully sorted, but splitting it at any midpoint always leaves at least one half sorted. The single point where the order breaks (the rotation point) can lie in only one of the two halves, so the other half is a clean ascending run.

At each step, determine which half is sorted, then decide where the target could be. Because a sorted half is bounded by its two endpoints, a range check on those endpoints tells us whether the target can be inside it. If it can, search that half. If it cannot, the target must be in the other half. Either way, half the array is discarded.

To determine which half is sorted, compare nums[left] with nums[mid]:

  • If nums[left] <= nums[mid], the left half [left...mid] is sorted.
  • Otherwise, the right half [mid...right] is sorted.

Algorithm

  1. Set left = 0 and right = nums.length - 1.
  2. While left <= right:
    • Compute mid = left + (right - left) / 2.
    • If nums[mid] == target, return mid.
    • Check if the left half is sorted (nums[left] <= nums[mid]):
      • If target is within [nums[left], nums[mid]), search left: right = mid - 1.
      • Otherwise, search right: left = mid + 1.
    • Otherwise, the right half is sorted:
      • If target is within (nums[mid], nums[right]], search right: left = mid + 1.
      • Otherwise, search left: right = mid - 1.
  3. If the loop ends without finding the target, return -1.

Example Walkthrough

1Initialize: left=0, right=6, target=0
0
4
left
1
5
2
6
3
7
4
0
5
1
6
2
right
search range
1/7

Code