Back to DSA
Search a 2D Matrix
easyYou are given an m-by-n matrix of integers where each row is sorted in ascending order and the first value of each row exceeds the last value of the row above it. Given a target integer, determine whether it exists in the matrix. Your solution should run in O(log(m*n)) time.
Examples
Example 1:
Input:
matrix = [[1,4,7],[10,13,16],[19,22,25]], target = 13Output:
trueExplanation: 13 appears in the second row.
Example 2:
Input:
matrix = [[1,4,7],[10,13,16],[19,22,25]], target = 14Output:
falseExplanation: 14 is not present in the matrix.
Hints
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length, n = matrix[0].length;
int lo = 0, hi = m * n - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
int val = matrix[mid / n][mid % n];
if (val == target) return true;
else if (val < target) lo = mid + 1;
else hi = mid - 1;
}
return false;
}
}Time complexity
O(log(m * n))Space complexity
O(1)