Search a 2D Matrix
LeetCode #74 · Medium · Binary Search · C++ solution with worked-out approach and complexity analysis.
Approach
Binary Search on Flattened Matrix
Key insight
Since the matrix is sorted row by row and the first element of a row is greater than the last element of the previous row, the entire matrix can be treated as a single sorted array of size m * n.
Strategy
- 1Treat the 2D matrix as a 1D array of size m * n.
- 2Perform standard binary search with range [0, m * n - 1].
- 3Map 1D index 'middle' back to 2D coordinates:
- 4Compare matrix[row][col] with target and adjust search range.
Time
O(log(m * n))
Space
O(1)
Problem description(from LeetCode)
You are given an m x n integer matrix matrix with the following two properties: 1. Each row is sorted in non-decreasing order. 2. The first integer of each row is greater than the last integer of the previous row. Given an integer target, return true if target is in matrix or false otherwise. You must write a solution in O(log(m * n)) time complexity.
Examples
Example 1
- Input:
- matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
- Output:
- true
Constraints
- •m == matrix.length
- •n == matrix[i].length
- •1 <= m, n <= 100
- •-10^4 <= matrix[i][j], target <= 10^4
C++ Solution
solution.cpp
class Solution {
public:
bool searchMatrix(vector<vector<int>> &matrix, int target) {
int m = matrix.size(), n = matrix[0].size();
int lo = 0, hi = m * n - 1;
while (lo <= hi) {
int middle = (lo + hi) / 2;
int i = middle / n;
int j = middle % n;
if (matrix[i][j] == target) {
return true;
} else if (matrix[i][j] > target) {
hi = hi - 1;
} else {
lo = lo + 1;
}
}
return false;
}
};