L14 · Binary Search II — Rotated & 2D

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

Watch first

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. 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. Row-and-column sorted 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.

First principles

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:                     # half-open on the answer: 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

Comparing to nums[hi] (not nums[lo]) is the correct pivot compass — it avoids an ambiguous case when the array isn't rotated.

Template C — search a row+col sorted matrix as one flat array

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

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.

The recall trap to avoid: in find-min, always compare to nums[hi], never nums[lo] — "the tail tells the truth."

The trap

What interviewers actually ask

Rotated-array search is a classic follow-up to plain binary search and a frequent Amazon/Microsoft/Meta question.

• Search in Rotated Sorted Array (33) · Medium · Amazon, Microsoft, Meta — 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 · Amazon — 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 · Amazon, Microsoft — probes: the pivot compass (compare to nums[hi]). Follow-up: with duplicates (154), worst-case O(n).
• Search a 2D Matrix (74) · Medium · Amazon, Microsoft — 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 · Amazon — probes: staircase from top-right (O(m+n)) when rows aren't globally chained. Follow-up: why binary search per row is worse than the staircase.
• Peak Index in a Mountain Array (852) · Medium · Amazon, Google — 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).

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 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

Where this shows up

Rotated-array search models lookups in circular buffers and log-structured storage where a sorted sequence wraps around a ring — you still binary search by first locating the wrap point. The 2D flatten trick is the same index arithmetic (row = i // width, col = i % width) used to address a pixel buffer or a flattened tensor in memory, where a logically 2D structure is stored as one contiguous sorted-or-indexable array.

Checkpoint

Quiz

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.