Binary search extends naturally to 2D matrices, but the approach depends on the matrix structure. A fully sorted matrix (sorted row-by-row) requires different logic than a matrix where each row and column is sorted independently.
This guide covers both approaches, when to use each, the index mapping formula, and complete templates for 2D matrix binary search.
Two matrix types:
Type 1: Fully sorted (treat as 1D array)
[1, 3, 5, 7]
[10, 11, 16, 20]
[23, 30, 34, 60]
Sorted row-by-row → Use binary search with index mapping
Time: O(log(m × n))Type 2: Row-column sorted (staircase search)
[1, 4, 7, 11]
[2, 5, 8, 12]
[3, 6, 9, 16]
[10, 13, 14, 17]
Each row sorted, each column sorted → Use staircase search
Time: O(m + n)Matrix is sorted row-by-row (last element of row i < first element of row i+1).
Key insight: A fully sorted matrix is just a 1D sorted array wrapped into 2D.
Index mapping:
1D index → 2D coordinates:
row = index // cols
col = index % cols
2D coordinates → 1D index:
index = row * cols + coldef searchMatrix(matrix: List[List[int]], target: int) -> bool:
"""
Search in fully sorted matrix
Time: O(log(m × n))
Space: O(1)
"""
if not matrix or not matrix[0]:
return False
rows, cols = len(matrix), len(matrix[0])
left, right = 0, rows * cols - 1
while left <= right:
mid = left + (right - left) // 2
# Convert 1D index to 2D coordinates
row, col = mid // cols, mid % cols
mid_value = matrix[row][col]
if mid_value == target:
return True
elif mid_value < target:
left = mid + 1
else:
right = mid - 1
return Falsematrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 60]
]
searchMatrix(matrix, 3) # True
# Trace:
# left=0, right=11, mid=5
# row=5//4=1, col=5%4=1
# matrix[1][1]=11 > 3 → right=4
# left=0, right=4, mid=2
# row=2//4=0, col=2%4=2
# matrix[0][2]=5 > 3 → right=1
# left=0, right=1, mid=0
# row=0//4=0, col=0%4=0
# matrix[0][0]=1 < 3 → left=1
# left=1, right=1, mid=1
# row=1//4=0, col=1%4=1
# matrix[0][1]=3 == 3 → True ✓Each row is sorted left-to-right, each column is sorted top-to-bottom, but NOT fully sorted overall.
Matrix:
[1, 4, 7, 11]
[2, 5, 8, 12]
[3, 6, 9, 16]
[10, 13, 14, 17]
Target = 5
If we treat as 1D: [1,4,7,11,2,5,8,12,3,6,9,16,10,13,14,17]
This is NOT sorted → binary search failsKey insight: Start from top-right (or bottom-left) corner. From there, you can eliminate either a row or column with each comparison.
Starting from top-right:
matrix[row][col] > target: eliminate column (move left)matrix[row][col] < target: eliminate row (move down)matrix[row][col] == target: found!Why this works:
def searchMatrix(matrix: List[List[int]], target: int) -> bool:
"""
Search in row-column sorted matrix
Time: O(m + n)
Space: O(1)
"""
if not matrix or not matrix[0]:
return False
rows, cols = len(matrix), len(matrix[0])
row, col = 0, cols - 1 # Start from top-right
while row < rows and col >= 0:
if matrix[row][col] == target:
return True
elif matrix[row][col] > target:
col -= 1 # Eliminate column
else:
row += 1 # Eliminate row
return Falsematrix = [
[1, 4, 7, 11],
[2, 5, 8, 12],
[3, 6, 9, 16],
[10, 13, 14, 17]
]
searchMatrix(matrix, 5) # True
# Trace (starting from top-right):
# row=0, col=3: matrix[0][3]=11 > 5 → col=2
# row=0, col=2: matrix[0][2]=7 > 5 → col=1
# row=0, col=1: matrix[0][1]=4 < 5 → row=1
# row=1, col=1: matrix[1][1]=5 == 5 → True ✓| Matrix Type | Approach | Time | Example |
|---|---|---|---|
| Fully sorted row-by-row | Binary search (1D mapping) | O(log(m×n)) | LeetCode #74 |
| Row and column sorted | Staircase search | O(m+n) | LeetCode #240 |
function searchMatrix(matrix, target) {
if (!matrix || !matrix.length || !matrix[0].length) return false;
const rows = matrix.length;
const cols = matrix[0].length;
let left = 0;
let right = rows * cols - 1;
while (left <= right) {
const mid = left + Math.floor((right - left) / 2);
const row = Math.floor(mid / cols);
const col = mid % cols;
const midValue = matrix[row][col];
if (midValue === target) {
return true;
} else if (midValue < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return false;
}public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return false;
}
int rows = matrix.length;
int cols = matrix[0].length;
int row = 0;
int col = cols - 1;
while (row < rows && col >= 0) {
if (matrix[row][col] == target) {
return true;
} else if (matrix[row][col] > target) {
col--;
} else {
row++;
}
}
return false;
}❌ Wrong:
row = mid % cols # WRONG
col = mid // cols # WRONG✅ Correct:
row = mid // cols # Correct
col = mid % cols # CorrectSee guide: 2D Matrix Index Mapping
❌ Wrong:
# Using binary search on row-column sorted matrix (not fully sorted)✅ Correct:
# Use staircase search for row-column sorted❌ Wrong:
right = rows * cols # WRONG: should be -1✅ Correct:
right = rows * cols - 1 # CorrectQ: Which approach is faster?
A: Binary search (O(log(m×n))) is faster than staircase (O(m+n)), but only works on fully sorted matrices.
Q: Can I use binary search on row-column sorted matrices?
A: Not directly. You'd need to binary search each row (O(m log n)) or use staircase search (O(m+n)).
Q: Why start from top-right in staircase search?
A: Top-right (or bottom-left) allows greedy elimination. Top-left or bottom-right don't work.
Q: What if the matrix is empty?
A: Handle edge cases: check if matrix, matrix[0] exist before accessing.
Binary search on 2D matrices requires choosing the right approach:
Fully sorted: Treat as 1D array with index mapping → O(log(m×n))
Row-column sorted: Use staircase search → O(m+n)
Master both techniques and you'll handle any 2D matrix search problem. For more details, see 2D Matrix Index Mapping and the Complete Binary Search Guide.
LeetCopilot is a free browser extension that enhances your LeetCode practice with AI-powered hints, personalized study notes, and realistic mock interviews — all designed to accelerate your coding interview preparation.
Also compatible with Edge, Brave, and Opera
Add to Chrome for free