33. Search in Rotated Sorted Array

Quick Identifier

Topic: binary-search
Pattern: Binary Search (Rotated, two ascents)
Difficulty: Medium
Companies: Amazon, Google, Meta, Bloomberg, Apple
Frequency: Very High
LeetCode: 33

Quick Sights

Time Complexity: O(log n) from the optimal approach.
Space Complexity: O(1) from the optimal approach.
Core Mechanism: Distinct integers sorted ascending then rotated once; return index of target, or -1. Required O(log n).

Concept Explanation

Distinct integers sorted ascending then rotated once; return index of target, or -1. Required O(log n).

The key is to state the invariant before coding: what part of the input is already settled, what state is still unresolved, and what single operation makes progress without losing correctness.

Recognition cues:

Rotated sorted + search target
Two increasing segments; one side of mid is always normally sorted
Test whether target lies in sorted half

Study Pattern (SDE3+)

0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

Loading diagram…

Approaches

Brute force — O(n) — scan.
Better — find pivot then vanilla BS — two passes still O(log n) if careful.
Optimal — O(log n) time / O(1) space — single binary search: decide left sorted vs right sorted half and whether target is in-range.

Optimal Solution

Go

func search(nums []int, target int) int {
	left, right := 0, len(nums)-1
	for left <= right {
		mid := left + (right-left)/2
		if nums[mid] == target {
			return mid
		}
		if nums[left] <= nums[mid] {
			if nums[left] <= target && target < nums[mid] {
				right = mid - 1
			} else {
				left = mid + 1
			}
		} else {
			if nums[mid] < target && target <= nums[right] {
				left = mid + 1
			} else {
				right = mid - 1
			}
		}
	}
	return -1
}

JavaScript

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