Every binary search in part one had a sorted array underneath it. Take that away and most people assume the technique goes with it. It does not — sortedness was never the requirement, only the most convenient way to meet it.
This is the second of three posts on Joseph Choi’s binary search session deck. Seven problems here, in two families: three where the array rises and then falls, and four where a sorted array has been rotated. In both, something other than the sort order tells you which half to keep.
As in part one, every listing was compiled with -Wall -Wextra -fsanitize=undefined,address and differentially tested against brute force before the prose was written, and the numbers in the closing section are measured.
What binary search actually requires
One paragraph of recap, because the whole post rests on it. Binary search needs a range of candidates and a yes/no question you can ask about any single one, whose answers run false, false, …, false, true, true, …, true — once the answer flips it never flips back. That property is called monotonicity, and it is the only requirement. A sorted array supplies it through “is nums[i] at least the target?”, which is false up to a point and true after it. Nothing says it has to come from there.
The two loop shapes, in brief. Template A is the closed interval, while (lo <= hi), which exits with lo == hi + 1 — so lo is the first true and hi is the last false. Template B is the converging interval, while (lo < hi) with hi = mid rather than hi = mid - 1, which never discards the current candidate and exits with exactly one index alive. Part one derives both and explains why mid = lo + (hi - lo) / 2 is not optional; if that is unfamiliar, start there.
Template B is the one that matters here. Both families in this post share a problem: there is no test you can apply to a single index in isolation. “Is this the peak?” needs both neighbours. “Which zone of the rotation am I in?” needs something to compare against. Template B handles both by keeping one candidate alive at all times.
Peaks: when the predicate is local
Three problems where the array is not sorted and never will be. What replaces sortedness is a local rule: comparing an element with its neighbour tells you which half must contain an answer. This is template B’s home.
Peak Index in a Mountain Array (LC 852, Medium)
The array strictly increases and then strictly decreases; find the turn.
int peakIndexInMountainArray(vector<int>& arr) {
int lo = 0, hi = (int)arr.size() - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2; // mid < hi, so arr[mid + 1] is always valid
if (arr[mid] < arr[mid + 1]) lo = mid + 1; // still climbing: the peak is to the right
else hi = mid; // mid could be the peak
}
return lo;
}The predicate is “am I still climbing?” — arr[mid] < arr[mid + 1]. True on the whole ascending side, false from the peak onward, which is monotone. If you are still climbing, mid is definitely not the peak and everything left of it is out too. If you are not, mid might be the peak, so keep it: hi = mid.
The deck’s version uses template A with an explicit three-way test — is mid a strict peak, is it on the way up, or on the way down — plus mid > 0 && mid < size - 1 guards to keep the neighbour reads in bounds. It works, and it makes the “three zones” framing from the slide visible in the code. Template B gets there with one comparison and no guards, because mid < hi is guaranteed by the loop condition. The trade is readability against safety-by-construction; I lean toward the version that cannot be indexed out of bounds.
Find Peak Element (LC 162, Medium)
Now drop the mountain guarantee. The array can zigzag arbitrarily; you need any index whose value is greater than both neighbours, with the ends treated as bordering negative infinity.
int findPeakElement(vector<int>& nums) {
int lo = 0, hi = (int)nums.size() - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] > nums[mid + 1]) hi = mid; // descending: a peak exists at or left of mid
else lo = mid + 1; // ascending: a peak exists right of mid
}
return lo;
}That is the same code as LC 852, with the comparison written the other way round, and that is the interesting part. The mountain guarantee was never what made the algorithm work. What makes it work is weaker: if nums[mid] > nums[mid + 1], then the half [lo, mid] must contain a peak, because either mid is one or the values keep rising as you walk left, and they cannot rise forever — they run into the boundary, which counts as negative infinity. The deck’s slide makes exactly this argument: if arr[mid] > arr[mid+1] then arr[mid+1] cannot be a peak and it is safe to set right = mid.
I checked this on 30,000 random arrays with no adjacent equal values, verifying that the returned index really is a strict local maximum rather than matching a specific expected answer — which is the right test for a problem that permits several correct outputs.
Find in Mountain Array (LC 1095, Hard)
A mountain array behind an API, and you want the smallest index holding a target. The deck’s decomposition is the standard one and it is correct: three binary searches — one for the peak, one up the ascending side, one down the descending side.
int findPeakIndex(MountainArray& arr) {
int lo = 0, hi = arr.length() - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (arr.get(mid) < arr.get(mid + 1)) lo = mid + 1; else hi = mid;
}
return lo;
}
int orderedSearch(MountainArray& arr, int target, int lo, int hi, bool ascending) {
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
int value = arr.get(mid);
if (value == target) return mid;
bool goRight = ascending ? (value < target) : (value > target);
if (goRight) lo = mid + 1; else hi = mid - 1;
}
return -1;
}
int findInMountainArray(int target, MountainArray& mountainArr) {
int peak = findPeakIndex(mountainArr);
int left = orderedSearch(mountainArr, target, 0, peak, true); // peak included: smallest index wins
if (left != -1) return left;
return orderedSearch(mountainArr, target, peak + 1, mountainArr.length() - 1, false);
}What makes this Hard is not the logic, it is the budget. get may be called at most 100 times and the array can hold 104 elements, so you have room for roughly three logarithmic passes and not much else. That single constraint is what rules out scanning and what makes the three-search structure necessary rather than elegant.
Measured at the maximum length with a target that is absent — the case where all three searches run to completion — the version above uses 53 calls. The deck’s version uses 64; both are comfortably inside the limit. The difference comes from the peak finder: the deck’s evaluates up to three get calls per iteration (current, previous, next) while template B needs two.
Two small structural choices. Including the peak in the ascending search rather than testing it separately removes a get and removes a branch. And searching ascending first is not arbitrary: the problem wants the smallest index, and if the target appears on both sides, the ascending side’s index is smaller by construction.
One line in the deck’s peak finder is worth flagging, because it is the sort of thing that is correct for a reason you have to go and find:
int nextVal = mid < end ? mountainArr.get(mid + 1) : INT_MIN;
// `end` shrinks as the search narrows, so at mid == end this treats the
// right-hand neighbour as negative infinity even when a real element sits
// there. It is still correct, but only because of the loop invariant: the
// peak is always inside [start, end], so if arr[mid] beats its left
// neighbour and mid is the last candidate, mid must be the peak.Rotated arrays, and the reference point
Four problems on a sorted array that has been rotated. The deck’s framing is two zones again: a high zone then a low zone, with everything in the second smaller than everything in the first. The skill is figuring out which zone you are standing in, and the tool for that is a reference point — a fixed element whose zone you already know.
Find Minimum in Rotated Sorted Array (LC 153, Medium)
The minimum is the first element of the low zone, so this is a boundary problem like all the others. What you need is a test for “which zone is mid in”, and the right-hand end of the window answers it.
int findMin153(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; // mid is in the high zone; the minimum is past it
else hi = mid; // mid is in the low zone and could be the minimum
}
return nums[lo];
}If nums[mid] > nums[hi], then mid is in the high zone and the minimum is strictly to its right. Otherwise mid is in the low zone and could be the minimum itself, so keep it. The unrotated case needs no special handling: every element is then at most nums[hi], the window collapses left, and index 0 is returned.
The deck uses template A with nums.back() — the original last element — as a fixed north star, and it is worth understanding why both work. A fixed reference works with template A because the window never contains the answer’s neighbourhood ambiguously; the live right end works with template B because the invariant keeps the minimum inside [lo, hi], which keeps nums[hi] in the low zone at every step. Mixing them up — a fixed reference in template B, or the live end in template A — is where this problem usually goes wrong.
Find Minimum in Rotated Sorted Array II (LC 154, Hard)
Same problem, duplicates allowed, and the deck names the difficulty precisely: with duplicates you can no longer tell which zone mid is in. When nums[mid] == nums[hi] the comparison gives you nothing.
int findMin154(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;
else if (nums[mid] < nums[hi]) hi = mid;
else --hi; // tie: hi cannot be the unique minimum unless mid also is
}
return nums[lo];
}The third branch is the whole difference, and the reason it is legal is subtle. If nums[mid] == nums[hi], then either hi is not the minimum — in which case dropping it loses nothing — or it is, and then mid holds the same value and is still in the window. Either way the minimum value survives. This works because the problem asks for the value, not the index; a variant that wanted the index of the minimum could not use this step.
The price is the complexity guarantee. --hi removes one element instead of half the window, so the worst case is O(n). Measured at n = 10,000: an all-equal array takes 9,999 iterations, while a distinct rotated array takes 14. That is not a flaw in the solution — you cannot do better. On [1,1,1,…,1] with a single 0 hidden somewhere, any algorithm that has not looked at a given position cannot rule out that position holding the 0, so Ω(n) reads are required. Being able to say that out loud is worth more in an interview than the code.
The deck reaches the same place differently: scan forward from the front while elements equal the last element, then binary search the remainder. Same O(n) worst case, same correctness, and it isolates the messy part into one line before the loop rather than into a branch inside it.
Search in Rotated Sorted Array (LC 33, Medium)
Now there is a target again. The deck states the key skill in one sentence, and it is the sentence to memorise: you need to spot the sorted part in any left/mid/right relationship.
int search33(vector<int>& nums, int target) {
int start = 0, end = (int)nums.size() - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (nums[mid] == target) return mid;
if (nums[start] <= nums[mid]) { // left half is genuinely sorted
if (target >= nums[start] && target < nums[mid]) end = mid - 1;
else start = mid + 1;
} else { // then the right half must be
if (target > nums[mid] && target <= nums[end]) start = mid + 1;
else end = mid - 1;
}
}
return -1;
}At least one of the two halves is always a genuine ascending run — a rotation can only put the break in one of them. So: identify the sorted half, check whether the target falls inside its range, and go there if it does or the other way if it does not. The nested ifs look fiddly but there are only four cases and each is a range containment test.
The <= in nums[start] <= nums[mid] is load-bearing and it is the most common way to lose this problem. When the window is one or two elements wide, mid == start, so nums[start] < nums[mid] is false and the code takes the “right half is sorted” branch — for a window where there is no right half. I ran both versions over 200,000 random rotations: <= failed zero times, < failed 37,566 times. The smallest counterexample is [3,1] searching for 1, which returns −1 instead of index 1.
Search in Rotated Sorted Array II (LC 81, Medium)
LC 33 with duplicates. The deck: when the duplicate is the mid value you cannot tell which zone the target is in, so fast forward until start and mid differ. Everything else is the same.
bool search81(vector<int>& nums, int target) {
int start = 0, end = (int)nums.size() - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (nums[mid] == target) return true;
if (nums[start] == nums[mid]) { ++start; continue; } // cannot tell which half is sorted
if (nums[start] <= nums[mid]) {
if (target >= nums[start] && target < nums[mid]) end = mid - 1;
else start = mid + 1;
} else {
if (target > nums[mid] && target <= nums[end]) start = mid + 1;
else end = mid - 1;
}
}
return false;
}Three lines added to LC 33, and they carry the same complexity penalty as LC 154 for the same reason. Measured at n = 5,000 on an array of all-equal values with the target absent: 2,500 loop iterations, against about 13 for a clean logarithmic search. And again, that is optimal rather than sloppy.
Note that the ambiguous case only requires giving up one element, not the half-window. It is tempting to write something more aggressive, but nums[start] == nums[mid] genuinely tells you only that start is not the answer — you already checked nums[mid] against the target on the line above.
The seven problems on one page
| Problem | What replaces sortedness | Predicate at mid | Template | Returns |
|---|---|---|---|---|
| 852 Peak Index | a local comparison | arr[mid] < arr[mid+1] | B | lo |
| 162 Find Peak | a local comparison | nums[mid] > nums[mid+1] | B | lo |
| 1095 Find in Mountain | peak first, then two sorted runs | peak, then ordered search | B then A | smallest matching index |
| 153 Min in Rotated | the live right end as reference | nums[mid] > nums[hi] | B | nums[lo] |
| 154 Min in Rotated II | same, ties broken by shrinking | same, plus --hi on a tie | B | nums[lo] |
| 33 Search Rotated | one half is always sorted | nums[start] <= nums[mid] | A | mid on a hit |
| 81 Search Rotated II | same, ties skipped one at a time | same, plus ++start on ties | A | true on a hit |
Two things stand out reading down that table. The peak problems and LC 153 use the same template with different comparisons, which is why they feel the same once you have written one. And the two duplicate-tolerant variants are their siblings plus one extra branch — a branch that costs the logarithm, as the next section measures.
Misfits, edge cases, and the things that bite
This family produces the sharpest edge cases in the whole deck, because the branching is comparison-based and comparisons collapse on narrow windows. Everything below was measured by running it.
One character decides LC 33
nums[start] <= nums[mid] versus nums[start] < nums[mid]. Over 200,000 random rotations the first failed zero times and the second failed 37,566 times. The smallest counterexample is two elements long: [3,1] searching for 1 returns −1 instead of index 1.
The mechanism generalises past this one problem. When the window narrows to one or two elements, mid collides with start, so any comparison between them degenerates — strict becomes false, non-strict becomes true, and whichever branch that picks had better be the harmless one. Test [1] and [3,1] by hand on anything in this family before you submit it.
Duplicates cost you the logarithm, and that is not your fault
LC 154 and LC 81 both degrade to O(n) in the worst case. Measured: LC 154 takes 9,999 iterations on 10,000 equal values against 14 on distinct ones; LC 81 takes 2,500 iterations on 5,000 equal values against about 13.
This is a lower bound, not a defect. Hide a single 0 in an array of 1s: any algorithm that has not read position i cannot rule out position i, so finding the minimum requires reading essentially everything. Saying that clearly is the correct answer to “can you do better?” — and it is a better answer than a cleverer-looking loop that is secretly wrong.
The peak problems need “no adjacent equals”
LC 162 guarantees nums[i] != nums[i+1] everywhere, and template B depends on it. Feed the same code a plateau such as [1,2,2,1] and it returns index 2, which is not a strict peak — and in that array no strict peak exists, so no algorithm could do better. Which is the point: the guarantee is not decoration, it is what makes the question answerable. When a variant allows equal neighbours, ask what “peak” is even supposed to mean before writing a loop.
When the probe is the expensive operation
LC 1095 is the problem where the API budget becomes the difficulty. get may be called at most 100 times and the array holds up to 104 elements, which leaves room for about three logarithmic passes and nothing else. Measured at the maximum length with an absent target — the case where all three searches run to completion — the version in this post uses 53 calls and the deck’s uses 64, against the limit of 100.
Both pass, so this is not a correctness note. It is a note about where the headroom comes from: the deck’s peak finder evaluates up to three get calls per iteration (current, previous, next) while template B needs two, and folding the “is the peak itself the target?” test into the ascending search removes one more. If the limit were 60 rather than 100, those choices would be the entire problem.
Do not mix a fixed reference with a shrinking window
LC 153 has two correct formulations and they are not interchangeable. The deck compares nums[mid] against nums.back() — the original last element, a fixed north star — inside template A. The version above compares against nums[hi], the live right end of the window, inside template B. Both work, for different reasons: the fixed reference is always in the high zone by definition, while the live end stays in the low zone because template B’s invariant keeps the minimum inside [lo, hi].
Swap them and you lose the argument. A fixed nums.back() with hi = mid can leave the window sitting entirely in the high zone with no way to tell; a live nums[hi] with hi = mid - 1 can discard the minimum and then compare against an element that is no longer meaningful. Pick one and keep the pairing.
LC 154 returns a value, and that is what makes it legal
The --hi tie-break in LC 154 is safe because of a detail in the problem statement rather than a property of the algorithm. When nums[mid] == nums[hi], either hi is not the minimum and dropping it loses nothing, or it is and mid holds the same value and stays in the window. The minimum value always survives. Its index may not.
So a variant that asked for the index of the minimum could not use that step, and neither could one that asked for the rotation count. That is a good thing to notice out loud, because “what exactly does the problem want back?” is the kind of question an interviewer is often testing rather than asking.
How to practise this
- Write template B from memory and say why
mid + 1needs no bounds check inside it. If you can answer that, the peak problems are done. - For each problem, name the thing that replaces sortedness before writing code: the neighbour, or the reference point.
- Trace
[3,1]and a single-element array by hand. Those two inputs catch most of the bugs above. - For anything with duplicates, state the worst case before you are asked. Both LC 154 and LC 81 are O(n), and saying so is a better answer than a cleverer loop that is secretly wrong.
- In order: 852 → 162 → 153 → 33 → 154 → 81 → 1095. The first two are the same code twice, 153 transfers template B to rotations, 33 introduces the sorted-half test, the two duplicate variants add the tie branch, and 1095 combines everything under an API budget.
The rest of this series
- Binary Search in C++: The Boundary Template and 10 Sorted-Array Problems — part one: both templates derived in full, the exit invariants, the
midoverflow, and the ten problems where the sort order supplies the predicate. LC 374, 278, 35, 744, 34, 1150, 74, 702, 540, 1060. - Binary Search on the Answer in C++: Five Problems With Nothing to Search — part three: no array at all. The search space is the set of possible answers and the input is only how you test a candidate. LC 69, 367, 441, 875, 1011.
Credit and the rest of the series
The problem selection, the ordering, and the framing come from Joseph Choi‘s binary search session deck — including the “two zones” reading of the rotated array, the reference-point idea, and the “spot the sorted part in any left/mid/right relationship” rule that makes LC 33 tractable. The C++ here is my own, rewritten where I preferred different bounds, types, or a different loop shape, and every listing was compiled and differentially tested before publication.
Other pattern write-ups on this site:
- Decrease and Conquer in C++: Twelve LeetCode Problems That Throw the Search Space Away — same instinct, applied where the discarded part is not a clean half.
- Monotonic Stack Pattern in C++: 13 LeetCode Problems, One Rule for Popping — thirteen problems decided by one question: what proves a candidate can never matter again?
- LeetCode Queue Design Patterns in C++: Put the Answer at an Edge — design problems where the work goes into keeping the answer reachable in O(1).
- LeetCode Linked List Patterns in C++: Recovering the Context a Node Doesn’t Have — what to do when a node knows nothing about where it sits.
- Prefix Sum in C++: Nine LeetCode Problems and One Equation — nine problems that collapse into a single subtraction.
- Cycle Sort in C++: Six LeetCode Array Problems That Are the Same Problem — when the values are a permutation of the indices, the array is its own hash table.