Find Minimum in Rotated Sorted Array — Binary Search on Sorted Halves
Use binary search to locate the pivot: if the mid element is greater than the rightmost element, search the right half; otherwise search the left.
Problem Statement
Given a rotated sorted array with no duplicates, return the minimum element.
Why This Problem Matters
- Shows how binary search adapts to problems where the sorted order is disrupted by a pivot.
- Encourages reasoning about invariants instead of blindly applying templates.
- Appears frequently as a warm-up to more complex binary-search-on-answer questions.
Thought Process
Check for already sorted segment
If nums[left] < nums[right], the array between them is sorted so nums[left] is the minimum.
Compare mid with right
If nums[mid] > nums[right], the pivot lies to the right; otherwise it lies to the left including mid.
Narrow the search space
Adjust left or right pointers based on the comparison until left == right.
Step-by-Step Reasoning
- Set left = 0, right = n - 1.
- While left < right, check if nums[left] < nums[right]; if so return nums[left].
- Compute mid; if nums[mid] > nums[right], set left = mid + 1 else set right = mid.
- Return nums[left] once the loop terminates.
Dry Run
nums = [4,5,6,7,0,1,2]
mid=3 > rightVal=2 → search right half; eventually left lands on index 4 (value 0).
nums = [1,2,3,4]
Initial check sees array sorted; return nums[0] immediately.
Complexity Analysis
Time
O(log n)
Space
O(1)
Why
Binary search halves the search space each iteration with constant extra storage.
Annotated Solution
public class FindMinimumInRotatedSortedArray {
public int findMin(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
if (nums[left] < nums[right]) {
return nums[left];
}
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) {
left = mid + 1;
} else {
right = mid;
}
}
return nums[left];
}
}Comparing the middle element with the rightmost element tells you which half remains rotated. Shrinking the search space accordingly homes in on the pivot.
Common Pitfalls
- Using mid = (left + right) / 2 without guarding against overflow (use left + (right - left) / 2).
- Forgetting the early-sorted check causes extra iterations but still works.
- Returning nums[mid] inside the loop can be wrong before convergence.
Follow-Up Questions
- How do you handle duplicates where nums[mid] == nums[right]?
- Can you return the index of the minimum instead of the value?