Approach Summary
The minimum is in the unsorted half. Compare mid with right: if arr[mid] > arr[right], minimum is to the right.
Full Solution & Approach
The rotation splits the array into two sorted halves, and the minimum is the pivot where the drop happens. Standard binary search still works if you compare mid against the right end. If nums[mid] is greater than nums[right], the rotation point lies to the right of mid — the minimum must be in the right half, so set left = mid + 1. Otherwise, mid is on the sorted tail, and the minimum is mid itself or to its left, so set right = mid. This asymmetric update (right = mid, not mid - 1) is what guarantees the loop terminates with left === right pointing at the minimum. When the array is not rotated at all, nums[mid] < nums[right] always holds and the search keeps pulling right toward 0, correctly returning the first element. The pattern generalizes: whenever one side of mid is sorted, you can decide which side holds the boundary.
Each iteration halves the range — O(log n) time. Constant space — O(1).
Solution Code
Solution
def find_min(nums: list[int]) -> int:
left, right = 0, len(nums) - 1
while left < right:
mid = (left + right) // 2
if nums[mid] > nums[right]:
left = mid + 1
else:
right = mid
return nums[left]function findMin(nums) {
let left = 0, right = nums.length - 1;
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (nums[mid] > nums[right]) left = mid + 1;
else right = mid;
}
return nums[left];
}public int findMin(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) left = mid + 1;
else right = mid;
}
return nums[left];
}int findMin(const vector<int>& nums) {
int left = 0, right = (int)nums.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) left = mid + 1;
else right = mid;
}
return nums[left];
}Edge Cases to Watch
- Not rotated at all — returns the first element
- Single element — returns it
- Rotation of one (last element moved to front) — the pivot is index 0
- All elements distinct per problem constraints
How to Recognize This Pattern
- Find pivot/minimum in rotated array
Complexity Analysis
Time Complexity
O(log n)
Space Complexity
O(1)