33. Search in Rotated Sorted Array

At a Glance

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

Problem (one-liner)

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

Recognition Cues

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

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

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;
}