02
Rotated / peak (Binary Search Sub-pattern)
The array isn't fully sorted, but some comparison at mid still tells you which half to keep: one half of a rotated array is always sorted, and a rising slope always leads to a peak.
Signals in the problem statement
- ›
"rotated at an unknown pivot"
- ›
"find the minimum" in a rotated array
- ›
"peak element"
- ›
"duplicates allowed" (the hard version)
What makes it different
The yes/no question is less obvious than nums[mid] < target. Find it first: nums[mid] > nums[hi] (the drop is to the right), or nums[mid] < nums[mid + 1] (climbing → a peak is to the right). With duplicates you sometimes can't decide, and the worst case becomes O(N).
Questions
ordered from “learn the idea” to “recognise it without help”- 1Find Minimum in Rotated Sorted ArrayWalkthroughMediumBasic Anchor·LeetCode #153
- 2Search in Rotated Sorted ArrayWalkthroughMediumSlight Variation·LeetCode #33
- 3Find Peak ElementWalkthroughMediumMedium·LeetCode #162
- 4Search in Rotated Sorted Array IIWalkthroughMediumTricky / Edge Case·LeetCode #81
Template
rotated-template.cpp
// Index of the minimum in a rotated sorted array (distinct values).
int findMinIndex(vector<int>& nums) {
int lo = 0, hi = (int)nums.size() - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] > nums[hi]) lo = mid + 1; // the drop is right of mid
else hi = mid; // mid..hi is sorted: the min is mid or left of it
}
return lo;
}Remember this · Binary Search
Trigger
Sorted data, "minimum X such that…", "maximum X such that…", rotated arrays, answers that are monotonic (if X works, X+1 also works).
Think
Is there a yes/no question whose answers look like NNNNYYYY? Then binary search for the first Y.
Key question
What is my check function, and is it monotonic?