Intermediate · Module 9 · Lesson 6
Matrix binary search
Map flat indexes into rows and columns.
15–25 min readLesson 52 of 123
Lesson 52 of 123
1d streakTheory lesson · Step-by-step
Understand Matrix binary search
Map flat indexes into rows and columns.
Worked approach
Trace the reasoning step by step
- 1Confirm global row-major sorted order.
- 2Binary-search indexes from 0 through rows×cols−1.
- 3Map mid into matrix coordinates.
- 4Compare and discard half.
Concrete example
Find 9 in a row-major sorted 3×4 matrix.
- 1Treat indexes 0…11 as one ordered range.
- 2Map flat index k to row k/4 and column k mod 4.
Binary search uses O(log(rows × cols)) comparisons.
What must remain true (Loop Invariant)
A flattened index maps to row = index / columns and column = index % columns.
Cost Model
Complexity & Trade-offs
OperationTimeSpaceWhy
Search
O(log n)
O(1)
Each valid decision removes half of a monotonic search space.When to use it
- Exact lookup, first/last occurrence, rotated order, and answer-space optimization.
- Any monotonic yes/no feasibility boundary.
- Implicit ordered spaces where values need not be materialized.
Common mistakes
- Mixing inclusive and half-open interval updates.
- Using binary search without proving monotonicity.
- Returning the last middle value instead of the stored boundary.
Practice prompts
- Reproduce the worked Matrix binary search example without looking at the trace.
- Change one input condition and explain whether the Matrix binary search invariant still holds.
- Implement the approach, derive its cost, and compare it with a straightforward baseline.
Mastery check
Can you derive it instead of memorizing it?
State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.