Binary Search on Rotated Arrays and Matrices

Plain binary search needs a sorted array. Interviewers rarely give you one. Instead they hand you an array that is almost sorted — rotated at an unknown pivot, or shaped like a mountain, or sorted along rows and columns of a matrix.

The unifying idea is broader than “sorted”:

Binary search works whenever you can look at mid and discard half the search space with certainty.

Sortedness is just the most familiar reason you can do that. This page covers the three other reasons that show up constantly.

What you’ll learn

• The “which half is sorted” test that handles rotation.
• Why lo < hi with hi = mid is the right loop shape for minimum/peak-finding, and lo <= hi with mid ± 1 for exact search.
• Peak finding: binary search with no sortedness at all, just a local gradient.
• The staircase walk for row/column-sorted matrices — $O(m + n)$, and not a binary search at all.
• Three real LeetCode problems solved in the browser: 33, 153, 162.

The cue

You are looking at a modified binary search when…

• The array is “sorted but rotated” — 33, 81, 153, 154.
• You must find a peak or the array is unimodal (“increases then decreases”) — 162, 852.
• The target is in a sorted matrix — 74 (fully sorted) or 240 (row/column sorted).
• len(nums) is up to $10^5$ and the problem says $O(\log n)$ — that requirement is the hint.
• You can answer “can I rule out one side?” at any index, even without full sortedness.

Two loop shapes, and when to use which

Getting these mixed up is the source of nearly every binary-search bug.

Goal	Loop	Update	Return
Find an exact value	while lo <= hi	lo = mid + 1 / hi = mid - 1	inside the loop, or -1
Find a boundary / minimum / peak	while lo < hi	lo = mid + 1 / hi = mid	lo after the loop

The second shape never uses hi = mid - 1, because mid might be the answer and must stay in range. It also cannot infinite-loop, because lo = mid + 1 always advances and hi = mid always shrinks (given mid < hi, which lo < hi guarantees with floor division).

Mixing them — lo < hi with hi = mid - 1 — silently skips the answer. lo <= hi with hi = mid hangs forever.

Visual intuition

The array is not sorted, but one half always is — and identifying which is the entire algorithm:

searchHalf of a rotated array is always sorted — find that half, then decideLC 33 · O(log n)

rotated

40516273041526

1def search_rotated(a, target):2    lo, hi = 0, len(a) - 13    while lo <= hi:4        mid = (lo + hi) // 25        if a[mid] == target: return mid6        if a[lo] <= a[mid]:              # LEFT half is sorted7            if a[lo] <= target < a[mid]: hi = mid - 18            else:                        lo = mid + 19        else:                            # RIGHT half is sorted10            if a[mid] < target <= a[hi]: lo = mid + 111            else:                        hi = mid - 112    return -1

target0

setupThe array is sorted but rotated, so it is not globally sorted and plain binary search fails. The insight: whatever the rotation, **at least one half of any window is properly sorted**, and you can test which in one comparison.

Play‹›1/5⟲

At every step compare nums[lo] with nums[mid]: if the left half is sorted, you can test the target against its endpoints exactly as in a normal binary search; otherwise the right half is sorted and you test there. The rotation never has to be located first.

Pattern 1 — rotated array, exact search

In a rotated sorted array, at least one half around mid is always properly sorted. Identify which, then check whether the target lies inside that sorted half: if yes, search it; if no, search the other.

search_rotated.py

def search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:                             # exact search shape
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
 
        if nums[lo] <= nums[mid]:               # LEFT half is sorted
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1                    # target is in the sorted left
            else:
                lo = mid + 1
        else:                                   # RIGHT half is sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1                    # target is in the sorted right
            else:
                hi = mid - 1
 
    return -1
 
 
print(search([4, 5, 6, 7, 0, 1, 2], 0))   # 4
print(search([4, 5, 6, 7, 0, 1, 2], 3))   # -1

Why nums[lo] <= nums[mid] and not <

When lo == mid (a two-element window), nums[lo] == nums[mid] and the “left half” is the single element nums[lo] — which is trivially sorted. Using strict < misclassifies this case and sends the search the wrong way on inputs like [3, 1] searching for 1.

Compare against nums[lo], not nums[hi], and keep the <=. That test case is in the exercise below precisely because it catches this.

Duplicates break the guarantee. In LC 81, nums[lo] == nums[mid] no longer tells you which side is sorted — consider [1,1,1,0,1]. The fix is to shrink one step (lo += 1) when nums[lo] == nums[mid] == nums[hi], which makes the worst case $O(n)$. That degradation is unavoidable, and saying so is the expected answer.

Pattern 2 — find the rotation point (minimum)

Here you want a position, not a value match, so use the lo < hi shape. Compare nums[mid] against nums[hi]:

find_min_rotated.py

def find_min(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:                       # boundary-finding shape
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1                 # minimum is strictly to the right
        else:
            hi = mid                     # mid could BE the minimum
    return nums[lo]
 
 
print(find_min([3, 4, 5, 1, 2]))       # 1
print(find_min([11, 13, 15, 17]))      # 11  (not rotated at all)

Compare with nums[hi], not nums[lo]. Against nums[lo] the not-rotated case ([11,13,15,17]) is ambiguous and needs a special case; against nums[hi] it falls out correctly with no extra branch.

Pattern 3 — peak finding, with no sortedness at all

LC 162 gives an array where neighbours differ, and asks for any index whose value is greater than both neighbours. The array is not sorted in any sense. Binary search still works:

find_peak.py

def find_peak_element(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < nums[mid + 1]:
            lo = mid + 1                 # we are ascending: a peak lies right
        else:
            hi = mid                     # descending: mid may be the peak
    return lo
 
 
print(find_peak_element([1, 2, 1, 3, 5, 6, 4]))   # 5 (or 1 -- both are peaks)

Why it is guaranteed to find one: if nums[mid] < nums[mid+1], the segment to the right starts by ascending, and since the array ends (treat the out-of-bounds neighbours as $-\infty$), it must turn down somewhere — so a peak exists in [mid+1, hi]. The same argument mirrors on the other side. The invariant “the current range contains a peak” is preserved, and the range shrinks every step.

This is the clearest demonstration that binary search is about discarding half with certainty, not about sorted data.

Pattern 4 — sorted matrices are two different problems

Problem	Structure	Technique	Complexity
74 Search a 2D Matrix	Fully sorted if flattened row-major	Binary search over m*n, with divmod(mid, cols)	$O(\log mn)$
240 Search a 2D Matrix II	Rows sorted, columns sorted, but rows do not continue from each other	Staircase walk from the top-right	$O(m + n)$

staircase_search_240.py

def search_matrix_ii(matrix, target):
    if not matrix or not matrix[0]:
        return False
    row, col = 0, len(matrix[0]) - 1        # start top-RIGHT
    while row < len(matrix) and col >= 0:
        value = matrix[row][col]
        if value == target:
            return True
        if value > target:
            col -= 1                        # this whole column is too big
        else:
            row += 1                        # this whole row is too small
    return False

The staircase is not a binary search

From the top-right corner, everything left is smaller and everything below is larger, so each comparison eliminates an entire row or column — one of $m + n$ total. It is $O(m + n)$, which for a square matrix is $O(\sqrt{mn})$ — worse than the $O(\log mn)$ of LC 74 but the best possible here, since LC 240’s weaker structure does not support halving.

Starting at the top-left or bottom-right does not work: from there, both directions increase (or both decrease), so no comparison can eliminate anything. Only the top-right and bottom-left corners have the needed opposition.

Dry run

Pattern 1 — search([4, 5, 6, 7, 0, 1, 2], 0)

lo	hi	mid	nums[mid]	Which half is sorted	Decision
0	6	3	7	left (nums[0]=4 <= 7)	0 is not in [4, 7) -> lo = 4
4	6	5	1	left (nums[4]=0 <= 1)	0 is in [0, 1) -> hi = 4
4	4	4	0	—	hit, return 4

Three iterations for seven elements. The rotation point was never located — the algorithm only ever asked “which side is sorted, and is the target inside it?” Row 2 is the one worth noticing: after discarding the left, the window [4, 6] holds [0, 1, 2], which is fully sorted, and the “left half is sorted” branch degenerates into an ordinary binary search. That is what always happens once the rotation point falls outside the window.

Why the guard is nums[lo] <= nums[mid] and not <

nums = [3, 1], target = 1. Two elements, so mid == lo == 0.

Guard	Trace	Result
<=	lo=0 hi=1 mid=0: left sorted, 1 not in [3, 3) -> lo = 1; then mid=1 hits	1 ✅
<	lo=0 hi=1 mid=0: classified as right sorted, 1 not in (3, 1] -> hi = -1	-1 ❌

With strict <, nums[lo] == nums[mid] == 3 fails the test, so the code concludes the right half is sorted — and then asks whether the target lies in (3, 1], an empty interval, which discards everything. A single element is trivially sorted; the <= says so.

This is the highest-value two-element test case on the page. [3, 1] searching 1 distinguishes a correct implementation from a plausible one in one call.

The duplicates degradation (LC 81), measured

Adding the nums[lo] == nums[mid] == nums[hi] shrink-by-one guard keeps the algorithm correct but costs the logarithm:

Input	Target	Found?	Iterations
[1, 1, 1, 0, 1]	0	yes	3
[1] * 30 + [0]	0	yes	5
[1] * 31	0	no	16

Row 2 stays logarithmic because nums[hi] is 0, so the three-way-equal guard never fires and the normal halving works. Row 3 is the genuine worst case: every window is all-ones, the guard fires every time, and lo += 1; hi -= 1 peels two elements per iteration — 16 iterations for 31 elements, which is $O(n)$, not $O(\log n)$. That degradation is unavoidable with duplicates, and saying so is the expected answer rather than a concession.

Pattern 2 — find_min, including the not-rotated case

[3, 4, 5, 1, 2]:

lo	hi	mid	Test against nums[hi]	Action
0	4	2	5 > 2	minimum is strictly right -> lo = 3
3	4	3	1 <= 2	mid could be it -> hi = 3

lo == hi == 3, minimum 1.

[11, 13, 15, 17] — not rotated at all:

lo	hi	mid	Test	Action
0	3	1	13 <= 17	hi = 1
0	1	0	11 <= 13	hi = 0

lo == hi == 0, minimum 11. No special case was needed. Every comparison took the hi = mid branch and walked the window down to index 0. Compare against nums[lo] instead and this input is ambiguous — nums[mid] > nums[lo] is true for a sorted array and for the left segment of a rotated one — which is exactly why the template compares against nums[hi].

Note the loop uses hi = mid, never hi = mid - 1. mid is a candidate answer and must stay in range; that is the whole distinction between the two loop shapes in the caution above.

Pattern 3 — find_peak_element([1, 2, 1, 3, 5, 6, 4])

lo	hi	mid	nums[mid] vs nums[mid+1]	Reading	Action
0	6	3	3 < 5	ascending	a peak lies right -> lo = 4
4	6	5	6 >= 4	descending	mid may be the peak -> hi = 5
4	5	4	5 < 6	ascending	-> lo = 5

Returns index 5, value 6. The array has two peaks — indices 1 and 5 — and the problem accepts either. Step 1 discarded index 1 permanently, which is fine: the guarantee is that the surviving range still contains a peak, not that no peak was discarded.

That invariant is the argument to give. If nums[mid] < nums[mid+1] the right side starts ascending, and since the array ends (treat out-of-bounds neighbours as $-\infty$) it must turn down somewhere, so [mid+1, hi] contains a peak. Nothing about the input is sorted; the discard is still certain, which is the real definition of binary search.

Pattern 4 — the staircase, and why it is not $O(\log mn)$

The LC 240 matrix, m = n = 5:

text

 1   4   7  11  15
 2   5   8  12  19
 3   6   9  16  22
10  13  14  17  24
18  21  23  26  30

target = 5, starting at the top-right (0, 4):

Cell	Value	vs 5	Eliminated	Move
(0,4)	15	>	column 4 entirely	col = 3
(0,3)	11	>	column 3	col = 2
(0,2)	7	>	column 2	col = 1
(0,1)	4	<	row 0	row = 1
(1,1)	5	=	—	found, 5 comparisons

target = 20, which is absent, takes the full walk: 9 comparisons, against m + n = 10. Each step retires one whole row or one whole column, so the walk cannot exceed m + n - 1 steps — and 20 nearly achieves it.

$O(m + n)$ is $O(\sqrt{mn})$ for a square matrix, genuinely worse than LC 74’s $O(\log mn)$. That is not a weaker algorithm; it is a weaker structure. LC 240’s rows do not continue from one another, so no single comparison can halve the search space, and $O(m+n)$ is the best available.

Starting anywhere else fails. From the top-left, both right and down increase, so a “too small” result eliminates nothing — you cannot tell which way to go. Same problem mirrored at the bottom-right. Only the top-right and bottom-left corners have one direction increasing and the other decreasing, and that opposition is exactly what makes each comparison decisive.

Complexity

Problem	Time	Space	The bound is set by
33 Search in Rotated Sorted Array	$O(\log n)$	$O(1)$	Halving; one side is always sorted
81 Same, with duplicates	$O(\log n)$ average, $O(n)$ worst	$O(1)$	The three-way-equal guard peels 2 per step — 16 iterations for [1]*31
153 Find Minimum in Rotated Array	$O(\log n)$	$O(1)$	Halving against nums[hi]
154 Same, with duplicates	$O(\log n)$ average, $O(n)$ worst	$O(1)$	Same degradation as 81
162 / 852 Find Peak / Peak in Mountain Array	$O(\log n)$	$O(1)$	Halving on the local slope, no sortedness needed
74 Search a 2D Matrix	$O(\log mn)$	$O(1)$	One binary search over the flattened index
240 Search a 2D Matrix II	$O(m + n)$	$O(1)$	One row or column retired per comparison

Four points worth stating precisely:

• All of these are $O(1)$ space. Every template here is iterative. A recursive binary search is $O(\log n)$ stack space for no benefit, and it is the version that hits CPython’s frame limit on a pathological input.
• $O(\log n)$ is a guarantee for 33 and 153, and only an average for 81 and 154. The difference is entirely the duplicates. If asked “can you keep it logarithmic with duplicates?”, the answer is no, with the reason: when nums[lo] == nums[mid] == nums[hi] there is genuinely no information about which side holds the target, so no correct algorithm can discard half.
• $O(m+n)$ versus $O(\log mn)$ is about the input, not the algorithm. For a $1000 \times 1000$ matrix that is ~2,000 steps against ~20. Both are fine; quoting 240 as $O(\log mn)$ is the mistake, and it usually means you did not notice the rows do not chain.
• (lo + hi) // 2 cannot overflow in Python. In C++ or Java it can, and the fix is lo + (hi - lo) // 2. Worth mentioning when the interviewer’s language is not Python — it shows you know why the idiom exists rather than copying it.

The variant map

Variant	The discard test	Canonical problem
Rotated, exact search	Which half is sorted, then is the target inside it	33
Rotated with duplicates	Same, plus lo += 1 when the test is ambiguous — $O(n)$ worst case	81 · 154
Rotation point	nums[mid] > nums[hi] means go right	153
Peak / unimodal	Compare nums[mid] with nums[mid+1]	162 · 852
Fully sorted matrix	Treat as 1D via divmod	74
Row/column sorted matrix	Staircase from a corner, $O(m+n)$	240

Practice — real LeetCode problems

LC 33 — Search in Rotated Sorted Array · Medium

Problem. An ascending array with distinct values was rotated at an unknown pivot. Given the rotated array and a target, return its index, or -1. You must write an $O(\log n)$ algorithm.

Constraints. 1 <= len(nums) <= 5000, all values unique, -10^4 <= nums[i], target <= 10^4.

Examples. nums = [4,5,6,7,0,1,2], target = 0 gives 4 · target = 3 gives -1 · nums = [1], target = 0 gives -1

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

A rotation splits the array into two ascending runs. Whatever mid is, the side of it that does not contain the rotation point is fully sorted, and for a sorted range you can test membership with two comparisons. So each iteration either finds the target or halves the range.

Time $O(\log n)$. Space $O(1)$.

([3, 1], 1) returning 1 is the case that punishes strict <: with lo=0, hi=1, mid=0, so nums[lo] == nums[mid] == 3. Only <= classifies the left half (just [3]) as sorted, correctly sending the search right.

A two-pass alternative is equally valid and some find it easier to defend: first find the rotation index with LC 153’s loop, then run an ordinary binary search on the appropriate segment. Two clean $O(\log n)$ passes beat one confusing one.

Follow-ups you should expect: “What if there are duplicates (LC 81)?” — when nums[lo] == nums[mid] == nums[hi] you cannot tell which side is sorted, so lo += 1 and continue; the worst case becomes $O(n)$ and that is provably unavoidable. “Find the rotation count?” — LC 153’s index. “Rotated descending array?” — mirror every comparison.

LC 153 — Find Minimum in Rotated Sorted Array · Medium

Problem. An ascending array of unique elements was rotated. Return its minimum element in $O(\log n)$.

Constraints. 1 <= len(nums) <= 5000, all values unique. The array may not actually be rotated.

Examples. [3,4,5,1,2] gives 1 · [4,5,6,7,0,1,2] gives 0 · [11,13,15,17] gives 11

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

The minimum is the single point where the array “drops”. Comparing nums[mid] to nums[hi] locates which side of mid that drop is on:

• nums[mid] > nums[hi] — the drop is between mid and hi, so the minimum is at mid + 1 or later.
• nums[mid] <= nums[hi] — the range mid..hi is ascending, so the minimum is at mid or earlier. mid stays in range: hi = mid.

Time $O(\log n)$. Space $O(1)$.

Two design choices carry the correctness:

• hi = mid, never mid - 1. mid is a live candidate; excluding it can skip the answer entirely.
• Compare against nums[hi]. With nums[lo], the un-rotated array [11,13,15,17] gives nums[mid] > nums[lo], which would push lo right and miss the minimum at index 0 — you would need an explicit “is it rotated?” pre-check. Against nums[hi] the case is handled for free.

Follow-ups you should expect: “With duplicates (LC 154)?” — when nums[mid] == nums[hi] you cannot decide, so hi -= 1; worst case $O(n)$. “Return the index instead?” — return lo. “How many times was it rotated?” — that is exactly the minimum’s index. “Find the maximum?” — mirror the comparison, or note it sits just left of the minimum.

LC 162 — Find Peak Element · Medium

Problem. A peak element is strictly greater than its neighbours. Given an array where nums[i] != nums[i+1] for all valid i, return the index of any peak. Imagine nums[-1] and nums[n] are $-\infty$. Must be $O(\log n)$.

Constraints. 1 <= len(nums) <= 1000, adjacent elements always differ.

Examples. [1,2,3,1] gives 2 · [1,2,1,3,5,6,4] gives 5 or 1 — both are peaks

Why this test checks “is it a peak”, not a fixed index

The problem explicitly accepts any peak, so the test below verifies that the index you return really is a peak (greater than both in-range neighbours) rather than demanding one particular answer.

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

The invariant is “the range [lo, hi] contains a peak”, and it holds initially because the out-of-range neighbours are $-\infty$ (so the global maximum is a peak).

Given nums[mid] < nums[mid+1], the range [mid+1, hi] starts by ascending. Either it keeps ascending to hi — making hi a peak, since its right neighbour is $-\infty$ — or it turns down somewhere, making that turning point a peak. Either way a peak exists to the right, so discarding [lo, mid] is safe. The mirror argument covers the other branch.

Time $O(\log n)$. Space $O(1)$.

mid + 1 is always a valid index: lo < hi plus floor division gives mid < hi, so mid + 1 <= hi. That is why the loop shape and the comparison have to agree — with lo <= hi you could have mid == hi and index out of bounds.

Note there is no nums[mid] > nums[mid-1] check anywhere. Verifying a true peak is unnecessary; maintaining the invariant is enough, and the loop exits only when lo == hi, which must then be a peak.

Follow-ups you should expect: “Find all peaks?” — that needs $O(n)$; a single linear scan, since peaks can be anywhere and halving would skip some. “What if neighbours can be equal?” — the guarantee collapses (consider a long plateau) and the worst case becomes $O(n)$. “2D peak (LC 1901)?” — binary search on columns, taking the row-max within each, giving $O(m \log n)$. “Mountain array (LC 852)?” — same code; the extra promise of exactly one peak changes nothing.

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

Recognise 74 and 240 as different problems

Both say “sorted matrix” and they are not the same. In LC 74 each row starts after the previous row ends, so the matrix is one sorted sequence and you get $O(\log mn)$. In LC 240 rows and columns are each sorted but rows overlap arbitrarily, so no global order exists and the best you can do is the $O(m+n)$ staircase.

Applying LC 74’s flatten-and-halve to LC 240 returns wrong answers on inputs a quick sample often misses. Read the constraints on how rows relate before choosing.

8 problems

0 easy7 medium1 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

AllEasyMediumHard

Unsolved onlyExportImportReset

• ○33Search in Rotated Sorted ArraymediumDecide which half is sorted, then test membershipNeetCode 150Blind 75LeetCode Top Interview 150amazonmetamicrosoftbloomberg
• ○74Search a 2D MatrixmediumFully sorted when flattened: binary search `m*n` with `divmod`NeetCode 150LeetCode Top Interview 150
• ○81Search in Rotated Sorted Array IImediumDuplicates make the test ambiguous; `lo += 1` and accept $O(n)$ worst case
• ○153Find Minimum in Rotated Sorted ArraymediumCompare with `nums[hi]`; `hi = mid`, never `mid - 1`NeetCode 150Blind 75LeetCode Top Interview 150
• ○162Find Peak ElementmediumNo sortedness at all -- just the local gradientLeetCode Top Interview 150
• ○240Search a 2D Matrix IImediumStaircase from the top-right, $O(m+n)$ -- not a binary search
• ○852Peak Index in a Mountain ArraymediumLC 162 with a guarantee of exactly one peak -- identical code
• ○154Find Minimum in Rotated Sorted Array IIhard153 with duplicates: `hi -= 1` on a tie, $O(n)$ worst case

Interview follow-ups

They ask	What they’re checking	The answer
“Why does binary search work without sorted data?”	Depth	All it needs is the ability to discard one half with certainty; sortedness is one way to earn that, a gradient or an invariant is another
“lo <= hi or lo < hi?”	Whether you pick deliberately	lo <= hi with mid ± 1 for exact search; lo < hi with hi = mid for boundaries — mid must stay a candidate
“What about duplicates?”	Knowing the limits	The which-half-is-sorted test becomes ambiguous; shrink one step and accept $O(n)$ worst case — it is provably unavoidable
“Why compare with nums[hi] in LC 153?”	Precision	Against nums[lo] the un-rotated array needs a special case; against nums[hi] it works unmodified
“Why is LC 240 not $O(\log mn)$?”	Reading structure	Rows overlap, so there is no single sorted order to halve; each step can only eliminate one row or one column
“Prove your loop terminates”	Rigour	lo = mid + 1 strictly advances and hi = mid strictly shrinks given mid < hi, which lo < hi plus floor division guarantees

Edge-case checklist

• Single element — every template must handle len == 1.
• Two elements — [3,1] for LC 33 (the <= test) and [2,1] for LC 153.
• Not actually rotated — [11,13,15,17]; the reason to compare with nums[hi].
• Rotated by exactly one — [5,1,2,3,4] and [2,3,4,5,1].
• Target absent — must return -1, not the nearest index.
• Target at the pivot — both the minimum and the element before it.
• Monotonic input for peak-finding — [1,2,3,4,5] peaks at the last index, [5,4,3,2,1] at the first; both exercise the $-\infty$ boundary.
• Empty matrix — guard matrix and matrix[0] before indexing.
• mid + 1 in range — only safe under the lo < hi shape.

Self-check

pch.quizTag pch.quizDefaultTitle

1. In the rotated-array search, why is the sortedness test `nums[lo] <= nums[mid]` rather than `nums[lo] < nums[mid]`?

   A To handle arrays containing duplicate values B When the window is two elements, mid == lo, so the values are equal -- a single element is trivially sorted and strict `<` misclassifies it C Because `<` would cause an infinite loop D The two are equivalent; `<=` is a style choice
   pch.quizShowAnswer

   B — When the window is two elements, mid == lo, so the values are equal -- a single element is trivially sorted and strict `<` misclassifies it — `nums = [3, 1]` searching for 1 is the test case. With `<=` the left half is (correctly) the single element 3, the target is not in [3, 3), so lo advances and the next iteration hits. With `<` the code decides the *right* half is sorted, asks whether 1 lies in (3, 1] -- an empty interval -- and discards everything, returning -1.

2. What is the worst-case time of rotated-array search when duplicates are allowed (LC 81)?

   A O(log n) still -- duplicates do not affect the halving B O(n), because when nums[lo] == nums[mid] == nums[hi] no side can be ruled out and you must shrink by one C O(n log n) D O(log^2 n)
   pch.quizShowAnswer

   B — O(n), because when nums[lo] == nums[mid] == nums[hi] no side can be ruled out and you must shrink by one — Measured: [1]*31 searching for 0 takes 16 iterations -- ceil(n/2), since the guard peels one element from each end. Note [1]*30 + [0] stays at 5 iterations because nums[hi] differs and the guard never fires, so the degradation needs the *whole window* equal. This is unavoidable: with all three probes equal there is genuinely no information about which side holds the target, so no correct algorithm can halve.

3. `find_min` compares `nums[mid]` against `nums[hi]`. What goes wrong comparing against `nums[lo]`?

   A Nothing -- both work identically B A non-rotated array becomes ambiguous: nums[mid] > nums[lo] holds both for a sorted array and for the left segment of a rotated one, so it needs a special case C It causes an infinite loop when the array has even length D It returns the maximum instead of the minimum
   pch.quizShowAnswer

   B — A non-rotated array becomes ambiguous: nums[mid] > nums[lo] holds both for a sorted array and for the left segment of a rotated one, so it needs a special case — Against nums[hi], [11, 13, 15, 17] falls out with no extra branch -- every comparison takes the `hi = mid` path and walks down to index 0. Against nums[lo] you cannot distinguish "not rotated at all" from "mid is in the left segment", which forces an up-front check of whether nums[0] <= nums[-1]. Correct, but a branch you did not need.

4. The boundary-finding loop uses `hi = mid`, never `hi = mid - 1`. Why?

   A To avoid a negative index B `mid` might be the answer, so it must stay inside the window; `hi = mid - 1` would discard it C Because `lo < hi` requires it to terminate D It makes the loop run one iteration fewer
   pch.quizShowAnswer

   B — `mid` might be the answer, so it must stay inside the window; `hi = mid - 1` would discard it — In an exact search, nums[mid] != target is proven before you move, so mid can be discarded. In a boundary search you are converging on a position, and mid is a live candidate until something better is found. Pairing `lo < hi` with `hi = mid - 1` silently skips the answer; pairing `lo <= hi` with `hi = mid` hangs forever. Those two mismatches are most binary-search bugs.

5. Peak finding works on an array with no sortedness at all. What is the invariant that makes it valid?

   A The array is unimodal, so it behaves like a sorted array B The surviving range always contains a peak: if nums[mid] < nums[mid+1] the right side starts ascending and must eventually turn down, since out-of-bounds neighbours count as negative infinity C Every array has a peak at its midpoint D The maximum element is always reachable by halving
   pch.quizShowAnswer

   B — The surviving range always contains a peak: if nums[mid] < nums[mid+1] the right side starts ascending and must eventually turn down, since out-of-bounds neighbours count as negative infinity — Binary search needs only the ability to discard half *with certainty* -- sortedness is one way to earn that, not the requirement. In the [1,2,1,3,5,6,4] trace the first step permanently discards the peak at index 1 and still returns the valid peak at index 5. The guarantee is about what survives, not about what is thrown away.

6. LC 74 is O(log mn) and LC 240 is O(m + n). Why the difference?

   A LC 240's algorithm is suboptimal; a binary search would do better B LC 240's rows do not continue from each other, so no single comparison can halve the space -- each one retires only a row or a column C LC 240 allows duplicate values D LC 74 is a smaller matrix in the constraints
   pch.quizShowAnswer

   B — LC 240's rows do not continue from each other, so no single comparison can halve the space -- each one retires only a row or a column — It is a difference in structure, not in cleverness. LC 74's matrix is one sorted sequence when flattened, so divmod plus one binary search works. LC 240 only guarantees each row and each column is sorted, which is strictly weaker. The measured walk for target 20 on a 5x5 matrix takes 9 comparisons against m + n = 10 -- close to the bound, and O(m+n) is the best available here.

7. Why must the staircase walk start at the top-right (or bottom-left), never the top-left?

   A The top-left holds the minimum, which is never the target B From a corner where both directions increase, a comparison eliminates nothing -- you cannot tell which way to move. Only the anti-diagonal corners have one direction increasing and the other decreasing C Because the loop condition `col >= 0` requires it D It works from the top-left too, but takes 2(m + n) steps
   pch.quizShowAnswer

   B — From a corner where both directions increase, a comparison eliminates nothing -- you cannot tell which way to move. Only the anti-diagonal corners have one direction increasing and the other decreasing — At the top-right, everything to the left is smaller and everything below is larger, so "too big" kills the column and "too small" kills the row -- every comparison is decisive. At the top-left both right and down increase, so a "too small" result leaves both directions open and you have learned nothing. That opposition is the whole reason the corner matters.

Recall card

• One half of a rotated array is always sorted. Find which, then ask whether the target lies inside it. The rotation point never needs locating.
• Test with nums[lo] <= nums[mid], <= not < — a one-element half is sorted. [3, 1] searching 1 is the test case that catches this.
• Two loop shapes, never mixed: exact value -> while lo <= hi with hi = mid - 1 · boundary or peak -> while lo < hi with hi = mid (because mid may be the answer), return lo.
• find_min compares against nums[hi], not nums[lo] — against nums[lo] the not-rotated case needs a special branch.
• Duplicates cost the logarithm. When nums[lo] == nums[mid] == nums[hi], shrink both ends by one: $O(n)$ worst case, 16 iterations for [1]*31. Unavoidable, and say so.
• Peak finding needs no sortedness — only that the surviving range still contains a peak. Binary search is about discarding half with certainty, not about sorted data.
• Two different matrix problems: LC 74 is fully sorted when flattened -> one binary search with divmod, $O(\log mn)$. LC 240 is row/column sorted only -> staircase from the top-right, $O(m + n)$.
• The staircase corner matters. Top-right or bottom-left only; from the top-left both directions increase and no comparison eliminates anything.
• All templates here are iterative and $O(1)$ space. lo + (hi - lo) // 2 if the language can overflow — Python cannot.

Recap

• Binary search needs only that you can discard half with certainty — not that the data is sorted.
• Rotated exact search: find the sorted half with nums[lo] <= nums[mid] (the <= matters), then test whether the target lies inside it.
• Two loop shapes: lo <= hi with mid ± 1 to find a value; lo < hi with hi = mid to find a boundary, minimum, or peak. Never mix them.
• Rotation point: compare nums[mid] with nums[hi], which handles the un-rotated array without a special case.
• Peak finding works on unsorted data via the local gradient, and the invariant “this range contains a peak”.
• Duplicates cost you the guarantee and degrade the worst case to $O(n)$ — say so rather than pretending otherwise.
• Sorted matrices split in two: fully sorted means $O(\log mn)$; row/column sorted means an $O(m+n)$ staircase from the top-right.

Next: Binary Search on Answer — searching a space of candidate answers rather than array indices.