AlgoMaster Logo

Search in Rotated Sorted Array

Last Updated: March 29, 2026

medium
3 min read

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.

The key observation is that 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 that range. If it does, we search left. If not, we search right. The same logic applies when the right half is sorted. This lets us eliminate half the array at each step, just like standard binary search.

Key Constraints:

  • 1 <= nums.length <= 5000 → With n up to 5000, even O(n) linear scan would be fast. But the problem explicitly requires O(log n), which means binary search.
  • All values of nums are unique → No duplicates simplifies the binary search logic. We can reliably determine which half is sorted by comparing nums[left] with nums[mid].
  • -10^4 <= target <= 10^4 → Standard integer range, no overflow concerns.

Approach 1: Linear Scan

Intuition

The most direct approach: just walk through the array and check every element. If we find the target, return its index. If we reach the end, return -1.

This completely ignores the sorted/rotated structure, which means it works on any array, not just rotated sorted ones. It's O(n), so it violates the problem's O(log n) requirement, but it's a clean baseline that makes it clear what we're trying to improve.

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 isn't fully sorted, but here's the crucial insight: when you split it at any midpoint, at least one half is always sorted.

So the algorithm is: at each step, figure out which half is sorted. Then check if the target could be in that sorted half (by comparing target to the half's endpoints). If yes, search that half. If no, search the other half.

How do we 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.

This works because the rotation point (the only place where order breaks) can be in at most one half.

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