Search in Rotated Sorted Array

Approach Summary

At each mid, determine which half is sorted. Use that to decide which half the target is in.

Full Solution & Approach

Binary search works here despite the rotation because at every step at least one half is fully sorted. Compute mid; if nums[mid] equals the target, return. Then check which side is sorted: if nums[lo] <= nums[mid], the left half is sorted — if the target lies within [nums[lo], nums[mid]), search left, otherwise search right. Otherwise the right half is sorted — if the target lies within (nums[mid], nums[hi]], search right, otherwise search left. The <= comparison in the left-half check handles the case where lo === mid. Each iteration eliminates roughly half the array just like standard binary search, so the run time is O(log n). The mental model: even though the array is rotated, one side of every mid is always monotonic, and you can trust that side's bounds to decide where the target must be.

Each step halves the search space — O(log n) time and O(1) space.

Solution Code

Solution

def search(nums: list[int], target: int) -> int:
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

function search(nums, target) {
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (nums[mid] === target) return mid;
    if (nums[lo] <= nums[mid]) {
      if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
      else lo = mid + 1;
    } else {
      if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
      else hi = mid - 1;
    }
  }
  return -1;
}

public int search(int[] nums, int target) {
    int lo = 0, hi = nums.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] == target) return mid;
        if (nums[lo] <= nums[mid]) {
            if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
            else lo = mid + 1;
        } else {
            if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
            else hi = mid - 1;
        }
    }
    return -1;
}

int search(const vector<int>& nums, int target) {
    int lo = 0, hi = (int)nums.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] == target) return mid;
        if (nums[lo] <= nums[mid]) {
            if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
            else lo = mid + 1;
        } else {
            if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
            else hi = mid - 1;
        }
    }
    return -1;
}

Edge Cases to Watch

Rotation point at index 0 (not actually rotated) — the algorithm reduces to standard binary search
Target at the rotation boundary
Single-element array
Array of length 2 where the rotation splits the two elements

How to Recognize This Pattern

Rotated sorted array
No pivot given

Complexity Analysis

Time Complexity

O(log n)

Space Complexity

O(1)