What signals in a problem statement indicate the 2D and partition search sub-pattern?

"each row is sorted and starts after the previous row ends"; "rows and columns are sorted"; "median of two sorted arrays" in O(log(m + n))

2D and partition search (Binary Search Sub-pattern)

Q: What makes 2D and partition search different from other sub-patterns?

The search space is an index you **compute** (`row = idx / n`, `col = idx % n`) or a **cut position**. LC 240 is here as the contrast: its best answer is a staircase walk, not binary search.

Search a sorted matrix as one flat sorted array, or binary search where to cut two sorted arrays so the left parts hold exactly half of everything.

Signals in the problem statement

›
"each row is sorted and starts after the previous row ends"
›
"rows and columns are sorted"
›
"median of two sorted arrays" in O(log(m + n))

What makes it different

The search space is an index you compute (row = idx / n, col = idx % n) or a cut position. LC 240 is here as the contrast: its best answer is a staircase walk, not binary search.

Questions

ordered from “learn the idea” to “recognise it without help”

1
Search a 2D Matrix
Basic Anchor·LeetCode #74
WalkthroughMedium
2
Search a 2D Matrix II
Medium·LeetCode #240
WalkthroughMedium
3
Median of Two Sorted Arrays
Tricky / Edge Case·LeetCode #4
WalkthroughHard

Template

exact-template.cpp

// Find target in a sorted array. Returns its index, or -1.
// Invariant: if target exists, it is inside [lo, hi].
int findValue(vector<int>& nums, int target) {
    int lo = 0, hi = (int)nums.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;      // same as (lo + hi) / 2, but can't overflow
        if (nums[mid] == target) return mid;
        if (nums[mid] < target) lo = mid + 1;   // target can only be to the right
        else hi = mid - 1;                      // target can only be to the left
    }
    return -1;
}

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?

Binary search on the answer