Search a 2D Matrix is Day 24 of the Tekraze DSA series, and it takes yesterday’s plain binary search and runs it on a grid. In Day 23, Binary Search, we searched a sorted array. Today we use that exact idea on a matrix. Once you see the trick, a grid stops looking scary and starts looking like one long sorted list.
Also Read: Day 23, Binary Search, covers the template we reuse today.
What is the Search a 2D Matrix problem?
You get an m x n integer matrix where every row is sorted from left to right. The first number of each row is bigger than the last number of the row above it. Given a target, return true if it is in the matrix and false otherwise. Your solution must run in O(log(m * n)) time. This is LeetCode problem 74 if you want to submit your own version.
text
Input: matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], target = 3 Output: true Input: matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], target = 13 Output: false
How should you think about Search a 2D Matrix in plain words?
Read the matrix row by row, like lines in a book. Because each row starts where the last one ended, you get 1, 3, 5, 7, 10, 11, 16, 20, 23 and so on, one fully sorted list. So why not pretend it really is one list?
If we can turn a single position into a row and a column, plain binary search does the rest.

What does the brute force Search a 2D Matrix approach look like?
Check every cell until you find the target.
python
def search_brute(matrix, target):
for row in matrix:
for x in row:
if x == target:
return True
return False
This takes O(m * n) time and O(1) space. It ignores all the sorting we were given, so it is far too slow for the O(log(m * n)) limit.
How do you get the optimal Search a 2D Matrix solution?
Treat the grid as a virtual array of length m * n. Set left = 0 and right = m * n - 1. For any middle index mid, the row is mid / n and the column is mid % n, where n is the number of columns. Compare that cell with the target and drop half the range, exactly like Day 23.
Walkthrough: searching for 13
The virtual array has 12 slots. Mid 5 maps to row 1, column 1, which is 11, so go right. Mid 8 maps to row 2, column 0, which is 23, so go left. Mid 6 is 16, so go left again. Now left is past right, the range is empty and we return false.
Time for Search a 2D Matrix is O(log(m * n)) because the range halves each step. Space is O(1) since we only store a few indexes. Some people binary search the rows first and then the columns. That is O(log m + log n), which is the same thing. If log time still feels fuzzy, our Big O helper post on time and space complexity breaks it down with charts.

Search a 2D Matrix solutions in Java, Python and Rust
Here is the same idea in all three languages. Each one is a few lines longer than plain binary search, and only the lookup line changes. The Java version uses a closed range like the one in the Java Arrays docs examples. Python has a built-in bisect module for 1D lists, but it does not take a 2D index, so we write the loop ourselves.
Search a 2D Matrix in Java
java
public class Solution {
public static boolean searchMatrix(int[][] matrix, int target) {
if (matrix.length == 0 || matrix[0].length == 0) return false;
int rows = matrix.length, cols = matrix[0].length;
int left = 0, right = rows * cols - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
int value = matrix[mid / cols][mid % cols];
if (value == target) return true;
if (value < target) left = mid + 1;
else right = mid - 1;
}
return false;
}
public static void main(String[] args) {
int[][] m = {{1, 3, 5, 7}, {10, 11, 16, 20}, {23, 30, 34, 60}};
check(searchMatrix(m, 3), true);
check(searchMatrix(m, 13), false);
check(searchMatrix(m, 1), true);
check(searchMatrix(m, 60), true);
check(searchMatrix(m, 0), false);
check(searchMatrix(m, 99), false);
check(searchMatrix(new int[][]{{5}}, 5), true);
check(searchMatrix(new int[][]{{5}}, 4), false);
check(searchMatrix(new int[][]{{1}, {3}}, 3), true);
check(searchMatrix(new int[0][0], 1), false);
System.out.println("All Java tests passed");
}
static void check(boolean got, boolean want) {
if (got != want) throw new AssertionError("got " + got + " want " + want);
}
}
Search a 2D Matrix in Python
python
def search_matrix(matrix, target):
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) // 2
value = matrix[mid // cols][mid % cols]
if value == target:
return True
if value < target:
left = mid + 1
else:
right = mid - 1
return False
if __name__ == "__main__":
m = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]]
assert search_matrix(m, 3) is True
assert search_matrix(m, 13) is False
assert search_matrix(m, 1) is True
assert search_matrix(m, 60) is True
assert search_matrix(m, 0) is False
assert search_matrix(m, 99) is False
assert search_matrix([[5]], 5) is True
assert search_matrix([[5]], 4) is False
assert search_matrix([[1], [3]], 3) is True
assert search_matrix([], 1) is False
print("All Python tests passed")
Search a 2D Matrix in Rust
Rust indexes are usize, so the Rust version uses the half open range from Day 23, where right sits one past the end. That way mid - 1 never underflows. The Rust slice docs show the same half open idea behind binary_search.
rust
fn search_matrix(matrix: &[Vec<i32>], target: i32) -> bool {
if matrix.is_empty() || matrix[0].is_empty() {
return false;
}
let cols = matrix[0].len();
let (mut left, mut right) = (0usize, matrix.len() * cols);
while left < right {
let mid = left + (right - left) / 2;
let value = matrix[mid / cols][mid % cols];
if value == target {
return true;
} else if value < target {
left = mid + 1;
} else {
right = mid;
}
}
false
}
fn main() {
let m = vec![vec![1, 3, 5, 7], vec![10, 11, 16, 20], vec![23, 30, 34, 60]];
assert!(search_matrix(&m, 3));
assert!(!search_matrix(&m, 13));
assert!(search_matrix(&m, 1));
assert!(search_matrix(&m, 60));
assert!(!search_matrix(&m, 0));
assert!(!search_matrix(&m, 99));
assert!(search_matrix(&[vec![5]], 5));
assert!(!search_matrix(&[vec![5]], 4));
assert!(search_matrix(&[vec![1], vec![3]], 3));
assert!(!search_matrix(&[], 1));
println!("All Rust tests passed");
}
Each program checks hits at the first, last and middle cells, misses below, above and between values, a single cell grid, a single column grid and an empty matrix. The Python version passes all ten checks when I run it.

What are the 6 tips and tricks for an easy Search a 2D Matrix solution?
Spot the pattern. A grid that reads as one sorted sequence row after row is just a sorted array wearing a costume.
Remember the mapping. Row is index / cols and column is index % cols. Always divide by the column count, not the row count.
Reuse your Day 23 template. Do not invent a new loop. Same left, right and mid, only the lookup changes.
Know the cousin problem. Search a 2D Matrix II only sorts rows and columns separately. There you start at the top right corner and step left or down in O(m + n).
Check the edge cases. Empty matrix, empty first row, a single row, a single column and targets outside the minimum and maximum.
Mention both approaches in interviews. Say the two step row then column approach out loud, then explain why the flattened view gives the same complexity with less code.
What are the common Search a 2D Matrix mistakes?
- Using
mid / rowsinstead ofmid / colsfor the row index, which breaks on non square grids. - Setting
right = m * nwith a closed range loop, which reads past the last cell. - Forgetting to check for an empty matrix before reading
matrix[0].length. - Using the corner walk from Search a 2D Matrix II here. It works, but it is O(m + n) instead of O(log(m * n)).
- Copying the grid into a real flat array first, which wastes O(m * n) space.
Where is the Search a 2D Matrix pattern used in the real world?
Flattening a 2D index into 1D is everywhere. Images store pixels in one long buffer and find pixel (row, col) with row * width + col. NumPy arrays use the same row major layout by default. Sorted data split into chunks, like log files or time series shards, can be searched as one range without loading everything.
Frequently asked questions
What is the Search a 2D Matrix problem?
You get a matrix where each row is sorted and each row starts after the previous row ends. You must say whether a target value exists in it in O(log(m * n)) time.
How do you convert a 1D index to a row and column?
For a matrix with n columns, row = index / n and column = index % n. This lets you binary search the matrix as if it were one sorted array.
What is the time complexity of Search a 2D Matrix?
The optimal solution runs in O(log(m * n)) time and O(1) extra space, because each step halves the virtual search range.
How is Search a 2D Matrix II different?
In Matrix II rows and columns are sorted separately, so the grid is not one sorted list. The usual approach starts at the top right corner and moves left or down in O(m + n) time.
Can I binary search rows first and then columns?
Yes. Find the row whose range holds the target, then binary search that row. It runs in O(log m + log n), which equals O(log(m * n)).
Conclusion
Search a 2D Matrix is binary search in a costume. Flatten the index, reuse the Day 23 loop and you are done. Next time Search a 2D Matrix shows up in an interview, you will know the trick. Today, try rewriting it with the row first approach, then compare how many more lines it takes.





