Find Minimum in Rotated Sorted Array Solution

Problem

A sorted array with no duplicates has been rotated at some unknown pivot, so [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]. Given the rotated array, return its minimum element without sorting it.

Input: [4, 5, 6, 7, 0, 1, 2]
Output: 0
Explanation: The original sorted order was rotated starting at index 4, placing 0 in the middle of the array.

A non-rotated array like [1, 3, 5] is also valid — the minimum is just the first element.

Intuition

Rotation splits the array into two sorted halves: a larger-valued left portion and a smaller-valued right portion. The minimum sits exactly at the transition between them. Because this structure exists, binary search can determine which half contains the transition point at every step, cutting the search space in half each time rather than scanning every element.

Approach 1 — Linear Scan

Scan every element and track the smallest value found. This ignores the sorted-halves structure entirely.

Initialize current_min to the first element.
Iterate through remaining elements one by one.
Update current_min whenever a smaller value is encountered.
Return current_min after the full scan.

1def findMin(nums: list[int]) -> int:
2    current_min = nums[0]
3    for value in nums[1:]:
4        if value < current_min:
5            current_min = value
6    return current_min

Time: O(n) — every element is visited exactly once.
Space: O(1) — only a single tracking variable is needed.

Approach 2 — Binary Search

Eliminate half the search space per step by exploiting the two-sorted-halves structure.

The key observation: if nums[mid] > nums[right], the left half is entirely greater than the right half's smallest element, so the minimum must be somewhere to the right of mid. Otherwise the minimum is at mid or to its left.

Set left = 0, right = len(nums) - 1.
While left < right, compute mid = left + (right - left) // 2.
If nums[mid] > nums[right], the inflection point is right of mid — set left = mid + 1.
Otherwise the inflection point is at mid or left of it — set right = mid (keep mid in range).
When left == right, the pointers have converged on the minimum — return nums[left].

1def findMin(nums: list[int]) -> int:
2    left, right = 0, len(nums) - 1
3
4    while left < right:
5        mid = left + (right - left) // 2
6
7        if nums[mid] > nums[right]:
8            # Left half is the "large" rotated portion; minimum is to the right
9            left = mid + 1
10        else:
11            # Mid could be the minimum itself, so don't exclude it
12            right = mid
13
14    return nums[left]

Time: O(log n) — the search space halves on every iteration.
Space: O(1) — only two index pointers are maintained.

Complexity Summary

Approach	Time	Space	When to use
Linear Scan	O(n)	O(1)	Array is small or unsorted — no structure to exploit
Binary Search	O(log n)	O(1)	Input is guaranteed to be a rotated sorted array with no duplicates

Common Mistakes

Comparing mid to left instead of right — comparing against the left boundary doesn't reliably identify which half contains the minimum, because the left element may or may not be in the "large" rotated portion. The right boundary is always in the smaller portion, making it the correct reference point.
Using right = mid - 1 instead of right = mid — when nums[mid] <= nums[right], mid itself might be the minimum. Excluding it with mid - 1 can skip the answer entirely.
Initializing right = len(nums) instead of len(nums) - 1 — this causes an out-of-bounds access when computing nums[right] inside the loop.
Using left <= right as the loop condition — this results in an infinite loop when left == right because neither branch changes both pointers when they're equal.
Integer overflow on mid calculation — (left + right) / 2 can overflow in Java and C++ with large indices. Always use left + (right - left) / 2.

Find Minimum in Rotated Sorted Array — Solution