Skip to main content
Binary Search

Rotated Sorted Array

A sorted array rotated at some pivot (e.g., [4,5,6,1,2,3]). At any midpoint, one half is definitely sorted. Check if the target falls in the sorted half — if yes, search there; if no, search the other half.

O(log n)
·
O(1)

How It Works

A rotated sorted array — such as [4,5,6,1,2,3] — is two sorted runs joined at a pivot. The key observation: at any midpoint, at least one of the two halves is fully sorted, and you can tell which by comparing the middle element with the boundary elements. Check whether the target lies within the sorted half's range; if it does, search there, otherwise search the other half.

Each comparison still discards half the array, preserving the O(log n) guarantee of ordinary binary search where a naive scan would take O(n). Duplicates weaken the guarantee: when nums[low], nums[mid], and nums[high] are all equal, you cannot tell which half is sorted and must shrink the bounds by one, degrading the worst case to O(n).

Step-by-Step Visualization

Search for 0 in rotated sorted array
L
4
0
5
1
6
2
mid
7
3
0
4
1
5
R
2
6
Target0
midnums[3]=7
1/4

Code

Java
static int searchRotated(int[] nums, int target) {
  int left = 0, right = nums.length - 1;

  while (left <= right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] == target) return mid;

    if (nums[left] <= nums[mid]) { // Left half sorted
      if (nums[left] <= target && target < nums[mid]) right = mid - 1;
      else left = mid + 1;
    } else { // Right half sorted
      if (nums[mid] < target && target <= nums[right]) left = mid + 1;
      else right = mid - 1;
    }
  }
  return -1;
}

// Example: searchRotated(new int[]{4,5,6,7,0,1,2}, 0) → 4

Tips & Gotchas

1One half is always sorted — determine which one
2Check if target falls in the sorted half; if so, search there
3Otherwise search the other (unsorted) half

Practice Problems

  • 1Search in Rotated Sorted Array
  • 2Search in Rotated Sorted Array II
  • 3Find Minimum in Rotated Sorted Array

About the Binary Search Pattern

If the search space is sorted (or has a monotonic property), you can eliminate half of it with each comparison. This reduces O(n) linear search to O(log n). Works on arrays, answer spaces, and even abstract conditions.

Key insight

When you see 'subarray', 'contiguous', or 'in-place', think arrays. The key is reducing brute-force O(n²) to O(n) using sliding window, two pointers, or prefix sums.

Common Array Interview Problems

  • Two Sum
  • Best Time to Buy & Sell Stock
  • Maximum Subarray
  • Merge Intervals
  • Product of Array Except Self
  • Container With Most Water

Frequently Asked Questions

How do I determine which half of a rotated array is sorted?

Compare nums[low] with nums[mid]: if nums[low] <= nums[mid], the left half is in order; otherwise the rotation point lies within it and the right half must be sorted. Exactly one boundary check then tells you whether the target can live in the sorted half.

Why do duplicate values break the O(log n) bound?

With duplicates, the case nums[low] == nums[mid] == nums[high] gives no information about which side contains the pivot, so the only safe move is shrinking the range by one element. An adversarial array of mostly equal values forces this repeatedly, making the worst case linear.

How does finding the minimum relate to searching in a rotated array?

The minimum sits exactly at the rotation point, found by binary searching toward the half that is out of order (compare mid against high). Once you know the pivot, a target search reduces to ordinary binary search in whichever sorted run could contain it.