Binary Search II — Rotated & 2D

Review boundary and corrected contracts

Flattening requires the entire row-major traversal to be nondecreasing, not merely independently sorted rows and columns. LC74 gives the stronger sufficient guarantee that each row starts strictly above the preceding row's last value; equality across a row boundary is also safe for binary search if the whole traversal remains sorted. A row/column-sorted matrix such as [[1,4],[2,5]] cannot use row-major binary search; staircase search or per-row binary search respects its weaker order. Rotation search without duplicates and the duplicate-tolerant variant have different worst-case bounds.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Learning objective: Binary search on a rotated sorted array by deciding which half is sorted, find the rotation minimum, and search a globally row-major sorted matrix by treating it as one flat sorted array.

Series: LeetCode — From Basics to Production-Ready · Session 14 / 65 · Phase 1 · Core patterns

Prerequisites. L13 (the binary search template) is required — you'll reuse its invariant and shrinking-range reasoning, but rotated search below uses a closed interval; the matrix search uses half-open bounds. Basic 2D-index math (row = idx // cols, col = idx % cols) is used for the matrix section.

Watch first

Optional companions from the original list: rotated search, rotation minimum, and matrix search. Compare their input contracts with the three templates below. The text is self-contained; external video availability is not verified here.

What this pattern IS

L13 assumed the array was sorted from front to back. Two very common twists break that assumption but still leave enough order to binary search:

1. Rotated sorted array with distinct values. A sorted array cut at some pivot and reattached: [4, 5, 6, 7, 0, 1, 2]. It's no longer globally sorted, so plain binary search fails. But here's the key fact: at least one half around any midpoint is still perfectly sorted. If you can tell which half is sorted, you can check whether the target lies inside that sorted half's range — if yes, search it; if no, search the other half. You still halve the space each step, so it's O(log n).

2. Globally row-major sorted rectangular matrix (each row sorted, first of each row > last of previous). This is just a sorted 1D array folded into a grid. Treat indices 0 .. rows*cols − 1 as one flat sorted array and convert mid to (mid // cols, mid % cols). One binary search, O(log(rows·cols)).

The unifying move: find the remaining monotone structure and search within it. Rotation hides the order in one half; the matrix hides it in a fold. Both are recovered by a single comparison at the midpoint.

A cut deck of sorted cards

Real: Someone cuts a sorted deck and puts the bottom part on top. Look at any card in the middle: comparing it to the top card tells you which side is still in perfect order. You search the ordered side if your card belongs there, otherwise the messy side.

if nums[lo] <= nums[mid]: left half sorted; else right half sorted.

First principles

Question: Why is at least one half of a rotated sorted array always sorted, and how does that let you binary search?

Premise: A rotated sorted array is two sorted runs: a higher run then a lower run (e.g. [4,5,6,7] then [0,1,2]).

Because: Rotating a strictly increasing array leaves at most one drop. An unrotated array or a search window wholly within one run has no drop; that is also safe.

Premise: Any midpoint splits the array into [lo..mid] and [mid..hi]; the single drop point can lie in only ONE of them.

Because: There is at most one break, so at most one half contains it — the other half is fully sorted. These endpoint comparisons assume distinct values; duplicates can hide the break.

Premise: Compare nums[lo] to nums[mid]: if nums[lo] <= nums[mid], the LEFT half is sorted; otherwise the RIGHT half is sorted.

Because: A sorted run has its start ≤ its end; the break shows up as a start > end.

Premise: In the sorted half, a range check (is target between its ends?) decides in O(1) whether to keep or discard it.

Because: The endpoint test excludes the sorted half when the target is outside its value range. If the target exists at all, it must then be in the other half; lying inside the range does not prove that an element equals it.

Premise: Each step discards half, preserving O(log n).

Because: Exactly one half is eliminated per iteration, same as ordinary binary search.

Conclusion: Identify the sorted half, range-check the target against it, keep or discard — one comparison recovers the binary search.

The templates

Template A — search in a rotated sorted array (no duplicates)

def search_rotated(nums, target):
    lo, hi = 0, len(nums) - 1          # closed interval here (we compare against nums[hi])
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:      # LEFT half [lo..mid] is sorted
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1           # target is in the sorted left half
            else:
                lo = mid + 1           # otherwise search the right
        else:                          # RIGHT half [mid..hi] is sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1           # target is in the sorted right half
            else:
                hi = mid - 1
    return -1

Template B — find the minimum (pivot) of a rotated sorted array

def find_min(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:                     # closed candidate interval: converge to the min
        mid = lo + (hi - lo) // 2
        if nums[mid] > nums[hi]:       # min must be to the RIGHT of mid
            lo = mid + 1
        else:                          # nums[mid] <= nums[hi]: min is at mid or LEFT
            hi = mid
    return nums[lo]                    # lo == hi == index of the minimum

For this template, compare to nums[hi]: it handles an unrotated window without a special case. find_min requires a nonempty rotation of distinct sorted values; an empty list has no minimum. Left-endpoint formulations can also work, but need different rules, such as returning nums[lo] first when the whole window is already sorted.

Template C — search a globally row-major sorted matrix as one flat array

The matrix case changes the job of the midpoint comparison. There is no rotation break to locate: the stated guarantee that each row starts above the previous row's last value makes the entire row-major walk sorted. Imagine joining the end of one row to the start of the next; division and remainder merely recover the cell at a position on that single walk. Rows and columns being individually sorted would not be enough to justify this flattening.

def search_matrix(matrix, target):
    if not matrix or not matrix[0]:
        return False
    rows, cols = len(matrix), len(matrix[0])
    lo, hi = 0, rows * cols            # flat index space, half-open
    while lo < hi:
        mid = lo + (hi - lo) // 2
        val = matrix[mid // cols][mid % cols]   # unflatten the 1D index to (row, col)
        if val == target:
            return True
        if val < target:
            lo = mid + 1
        else:
            hi = mid
    return False

Mental model

Name: One half is honest

Picture: A rotated array is two sorted ramps. At any midpoint, one side is a clean ramp. Ask 'does my target live on the clean ramp?' — if yes, go there; if no, the answer is on the other ramp. A sorted matrix is a single ramp folded into rows: unfold with //cols and %cols.

• Rotated: compare nums[lo] vs nums[mid] to find the sorted half.

• Range-check target against the sorted half's ends; keep or discard.

• Find-min: compare nums[mid] vs nums[hi]; min is where the ramp restarts.

• Matrix: flat index mid -> (mid // cols, mid % cols), then plain binary search.

Trigger: 'rotated sorted array', 'find the minimum / pivot', 'search a matrix sorted row-wise where each row starts above the previous'.

Memory / mnemonic

Two compasses and one fold — that's the whole session.

• Search rotated → the compass is "left-start vs mid." nums[lo] <= nums[mid] ⇒ left ramp is honest. Peg: "if the start is below the middle, the left is settled." Then range-check and keep/toss.
• Find min → the compass is "mid vs right." nums[mid] > nums[hi] ⇒ the drop is to the right ⇒ go right. Peg: "bigger than the tail? the valley's ahead."
• Matrix → the fold: "divide by cols for the row, mod cols for the col." Say "slash-cols, mod-cols" while typing mid // cols, mid % cols.

For this find-min template, the recall peg is "the tail tells the truth." Do not swap in nums[lo] without changing the invariant and handling already-sorted windows.

The trap

Myth: For find-minimum in a rotated array you should compare nums[mid] to nums[lo].

Truth: Use nums[hi] with the displayed update rules. A naive substitution of nums[lo] mishandles the already-sorted case; a separately proved left-endpoint algorithm is not inherently wrong.

Why: If nums[mid] > nums[hi], the rotation break is strictly to the right, so the minimum is right of mid. Comparing to nums[lo] gives no clean signal when the current window is already sorted (nums[lo] <= nums[mid] is true both when rotated far and not at all).

Test: Run find-min on an UN-rotated array like [1,2,3,4,5]. The nums[hi] version returns 1 correctly; a naive nums[lo] comparison can walk the wrong direction.

What reviewers actually ask

These practice problems exercise distinct input contracts; the list is not a claim about company-specific interview frequency.

• Search in Rotated Sorted Array (33) · Medium · Practice selection. — probes: can you identify the sorted half and range-check? Follow-up: what if duplicates are allowed (81)?
• Search in Rotated Sorted Array II (81) · Medium · Practice selection. — probes: duplicates break the nums[lo] <= nums[mid] test; handle nums[lo] == nums[mid] by shrinking lo. Follow-up: worst-case O(n) — why?
• Find Minimum in Rotated Sorted Array (153) · Medium · Practice selection. — probes: the pivot compass (compare to nums[hi]). Follow-up: with duplicates (154), worst-case O(n).
• Search a 2D Matrix (74) · Medium · Practice selection. — probes: flatten to one index space vs a staircase walk. Follow-up: the row+col-sorted-only variant (240), where flattening doesn't apply.
• Search a 2D Matrix II (240) · Medium · Practice selection. — probes: staircase from top-right (O(m+n)) when rows aren't globally chained. Follow-up: compare O(m log n) per-row search with O(m+n) staircase search for the actual matrix shape.
• Peak Index in a Mountain Array (852) · Medium · Practice selection. — probes: binary search on a non-sorted-but-monotone-then-monotone shape. Follow-up: find a peak in an arbitrary array (162).

Universal probe: "the array isn't fully sorted — where's the structure you can still exploit?" Name the sorted half or the fold.

Worked solutions

1. Search in Rotated Sorted Array (33)

Plain words: a sorted array was rotated at an unknown pivot; find the index of target, or −1. No duplicates.

Brute force: linear scan, O(n) — ignores the structure. Insight: at each midpoint one half is sorted; range-check the target against that half to decide where to go.

def search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:              # left half sorted
            if nums[lo] <= target < nums[mid]: # target inside sorted left
                hi = mid - 1
            else:
                lo = mid + 1
        else:                                  # right half sorted
            if nums[mid] < target <= nums[hi]: # target inside sorted right
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

Complexity: O(log n) time, O(1) memory. Follow-up — "with duplicates" (LC81): when nums[lo] == nums[mid] you can't tell which half is sorted, so do lo += 1 and retry; this degrades to O(n) in the worst case (e.g. all equal).

Goal: Return True/False for whether target EXISTS, handling duplicates (LC81).

Hint: Add a branch: if nums[lo] == nums[mid] == nums[hi], shrink both ends by one.

def searchDup(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            return True
        if nums[lo] == nums[mid] == nums[hi]:  # ambiguous -> shrink
            lo += 1
            hi -= 1
        elif nums[lo] <= nums[mid]:
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return False

2. Find Minimum in Rotated Sorted Array (153)

Plain words: a nonempty sorted array rotated at an unknown pivot; return the smallest element. No duplicates.

Insight: the minimum is the point where the ramp restarts. Compare nums[mid] to nums[hi]: if nums[mid] > nums[hi], the drop is to the right, so the min is right of mid; otherwise it's mid or left.

def findMin(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] > nums[hi]:      # minimum is strictly to the right
            lo = mid + 1
        else:                         # minimum is mid or to the left
            hi = mid
    return nums[lo]

Complexity: O(log n) time, O(1) memory. Follow-up — "with duplicates" (LC154): when nums[mid] == nums[hi], you can't decide, so do hi -= 1; worst case O(n) when many equal values hide the pivot.

3. Search a 2D Matrix (74)

Plain words: an m×n matrix where each row is sorted and the first element of each row is greater than the last of the previous row; return whether target is present.

Insight: the matrix is a single sorted sequence folded into rows. Binary search the flat index range [0, m*n) and convert mid back to (row, col) with divmod.

def searchMatrix(matrix, target):
    if not matrix or not matrix[0]:
        return False
    rows, cols = len(matrix), len(matrix[0])
    lo, hi = 0, rows * cols
    while lo < hi:
        mid = lo + (hi - lo) // 2
        r, c = divmod(mid, cols)      # unflatten
        val = matrix[r][c]
        if val == target:
            return True
        if val < target:
            lo = mid + 1
        else:
            hi = mid
    return False

Complexity: O(log(m·n)) time, O(1) memory. Follow-up — "rows and columns individually sorted but NOT globally chained" (LC240): flattening no longer works; walk a staircase from the top-right, moving left when too big and down when too small, for O(m + n).

Tradeoff

Decision: Search a 2D matrix for a target.

Name: Flatten + binary search

Gain: O(log(m·n)) worst-case comparisons without allocating a flattened copy.

Cost: Requires globally nondecreasing row-major order. LC74 supplies the stronger sufficient property: each row's first > previous row's last; separate row/column order alone is insufficient.

Pick: LC74-style matrices where the grid is one folded sorted array.

Name: Staircase from top-right

Gain: O(m + n); works with the WEAKER property (rows and cols each sorted only).

Cost: Linear, not logarithmic; more comparisons on large square matrices.

Pick: LC240-style matrices where rows aren't globally chained.

Name: Binary search each row

Gain: Simple to write.

Cost: O(m log(n+1)); for square matrices this is asymptotically worse than O(m+n), but for one very long row it is better.

Pick: A small number of long rows, or when rows are sorted but columns are not.

Verdict: Use flatten+binary-search for globally chained rows (74). For row/column-sorted matrices (240), compare staircase O(m+n) against per-row O(m log(n+1)) or per-column O(n log(m+1)); matrix shape matters.

The staircase has a different elimination proof: at the top-right remaining cell, a value larger than the target excludes its entire column below (all are at least as large); a smaller value excludes its entire row to the left (all are at most as small). Each step deletes one row or column.

def search_staircase(matrix, target):
    if not matrix or not matrix[0]:
        return False
    r, c = 0, len(matrix[0]) - 1
    while r < len(matrix) and c >= 0:
        value = matrix[r][c]
        if value == target:
            return True
        if value > target:
            c -= 1
        else:
            r += 1
    return False

On [[1, 4], [2, 5]], target 4 is found at the first staircase cell. Flattening gives [1, 4, 2, 5]; the displayed binary search sees 2, moves right, and misses 4. Both matrix implementations require a rectangular matrix, not ragged rows.

Where this shows up

A circular buffer containing a logically sorted sequence can illustrate rotated search; an arbitrary ring buffer is not necessarily sorted and does not acquire this search guarantee just by wrapping. The matrix index arithmetic (row = i // width, col = i % width) also addresses row-major pixel buffers and tensors, but addressability is not sortedness: binary search additionally needs the value-order contract.

Checkpoint

You can now…

• Identify which half of a rotated array is sorted with one comparison.

• Range-check the target against the sorted half to decide the next window.

• Find the rotation minimum by comparing nums[mid] to nums[hi].

• Handle duplicates by shrinking the boundary and explain the O(n) worst case.

• Flatten a globally-chained matrix and binary search its index space.

• Choose the top-right staircase for weaker row/col-sorted matrices.

Quiz

Self-check (answer follows each question).

Recall check

Q: In a rotated array, which comparison tells you the LEFT half is sorted?

A: With distinct values, nums[lo] <= nums[mid] identifies the sorted left half. With duplicates, equal endpoints can hide a rotation and require the ambiguity branch.

Q: Once you know a half is sorted, how do you decide whether the target is in it?

A: After testing the midpoint for equality, range-check the sorted half with the endpoint inequalities in the code. This identifies the only half that could contain the target; the target may still be absent.

Q: For Find Minimum, why compare nums[mid] to nums[hi] rather than nums[lo]?

A: nums[mid] > nums[hi] cleanly means the pivot (min) is to the right; the nums[lo] comparison is ambiguous when the current window is already sorted.

Q: How do you convert a flat index mid into matrix coordinates?

A: row = mid // cols, col = mid % cols (i.e. divmod(mid, cols)).

Q: Why does the flatten trick fail for a matrix that's only row-sorted and column-sorted (LC240)?

A: Rows aren't globally chained (a row's first element may be less than the previous row's last), so the grid isn't a single sorted sequence — flattening isn't monotone.

Q: ★ Stretch: why does duplicate handling in rotated search degrade to O(n)?

A: When nums[lo] == nums[mid] == nums[hi] you can't tell which half is sorted, so you shrink the ends by one instead of halving; an all-equal array with an absent different target forces this until the window empties, giving O(n). A mostly equal array with one hidden distinct target can also require linear work.

Stretch: true

Practice queue

+7d / +21d mark spaced-repetition anchors.

• Find Minimum in Rotated Sorted Array (153) — Medium · the pivot compass · +7d anchor.
• Search in Rotated Sorted Array (33) — Medium · which-half-is-sorted · +21d anchor.
• Search a 2D Matrix (74) — Medium · flatten + binary search.
• Peak Index in a Mountain Array (852) — Medium · binary search on a monotone-then-monotone shape.
• Search in Rotated Sorted Array II (81) — Medium · duplicates.
• Find Minimum in Rotated Sorted Array II (154) — Hard · duplicates + O(n) worst case.
• Search a 2D Matrix II (240) — Medium · the top-right staircase.

Corrective source notes

• Binary Search - Algorithms for Competitive Programming — Binary search can find a transition in an arbitrary monotone Boolean predicate. Checked 2026-10-07.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.