Search in Rotated Sorted Array

MediumBinary SearchArrayBinary Search

Problem

An array of distinct integers, originally sorted in ascending order, has been rotated at some unknown pivot so it wraps around partway through. Given a target value, return its index if present, or -1 otherwise.

Example. For [4, 5, 6, 7, 0, 1, 2] and a target of 0, the answer is index 4.

Key idea

A plain binary search assumes the whole range is sorted, which is no longer true here. But at any midpoint, at least one of the two halves is guaranteed to still be in plain ascending order, since only one seam exists in the whole array. The trick is to first identify which half is the sorted one, then apply ordinary sorted-range reasoning to decide whether the target could be in it.

At each step, compare the values at the low and mid boundaries. If low is less than or equal to mid, the left half is sorted, so check whether the target falls within that half's range and search there if so, otherwise search the right half. If instead the right half is the sorted one, apply the same check to it. One comparison determines which half is safe to reason about with normal sorted-array logic, and the unsorted half is explored only when the target cannot be in the sorted one.

Solution

function search(nums: number[], target: number): number {
  let low = 0;
  let high = nums.length - 1;

  while (low <= high) {
    const mid = low + Math.floor((high - low) / 2);

    if (nums[mid] === target) {
      return mid;
    }

    if (nums[low] <= nums[mid]) {
      // left half is sorted
      if (nums[low] <= target && target < nums[mid]) {
        // target falls inside the sorted left half
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    } else {
      // right half is sorted instead
      if (nums[mid] < target && target <= nums[high]) {
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    }
  }

  return -1;
}

Complexity

  • Time: O(log n). One comparison per step still discards half the remaining range.
  • Space: O(1). Only the low, high, and mid indices are tracked.

Watch out for

  • Use inclusive range checks against the sorted half's endpoints rather than assuming the sorted half is always the left one.
  • Distinct values are typically assumed; duplicates can make it impossible to tell which half is sorted from a single comparison.

Pattern

This is binary search with a sortedness check layered on top: decide which half obeys the simple sorted-array invariant, then apply standard target-range logic to that half only. Together with locating the rotation point, it forms the core toolkit for a sorted sequence that has been cut and reattached.

Related questions