153. Find Minimum in Rotated Sorted Array

At a Glance

• Topic: binary-search
• Pattern: Binary Search (Rotation / pivot)
• Difficulty: Medium
• Companies: Amazon, Google, Meta, Bloomberg, Microsoft
• Frequency: High
• LeetCode: 153

Problem (one-liner)

Given a sorted array rotated once around an unknown pivot (all distinct), return the minimum element in O(log n) time.

Recognition Cues

• Rotated sorted array, distinct values
• Minimum / pivot / “how many times rotated”
• Compare mid to right to decide which half contains the minimum

Diagram

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

Approaches

• Brute force — O(n) time / O(1) space — linear scan for minimum.
• Better — not applicable beyond BS.
• Optimal — O(log n) time / O(1) space — if nums[mid] > nums[right], minimum is right of mid; else left half including mid.

Optimal Solution

Go

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

JavaScript

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

Walkthrough

nums = [3,4,5,1,2]

Stop at index 3, value 1. Invariant: minimum remains inside [left, right].

Edge Cases

• Not rotated at all (full ascending) — answer is nums[0].
• Length 1.
• Two elements — smaller one is min.

Pitfalls

• Comparing only to nums[left] — ambiguous with duplicates removed here but wrong instinct for variants.
• Using <= wrong with duplicate-inclusive variants (use problem 154 logic instead).

Similar Problems

• 33. Search in Rotated Sorted Array — adds target test inside partitions.
• 162. Find Peak Element — compare neighbors to shrink side.
• 704. Binary Search — baseline halving without rotation.

Variants

• Allow duplicates — may degrade to O(n) worst case; compare three-way with left/mid/right.
• Find rotation count — index of minimum.

Mind-Map Tags

#binary-search #rotated-array #pivot #compare-to-right