Problem
Given an m x n integer matrix where each row is sorted in ascending order and the first integer of each row is greater than the last integer of the previous row, returntrue if target exists in the matrix. Otherwise, return false.
Example(s)
Example 1
Input
matrix =
[[1,3,5,7],
[10,11,16,20],
[23,30,34,60]]
target = 3Output
trueExample 2
Input
matrix =
[[1,3,5,7],
[10,11,16,20],
[23,30,34,60]]
target = 13Output
falseSolution
This problem uses Binary Search. Since every row is sorted and each row starts after the previous row ends, the entire matrix can be treated as one sorted 1D array.For a flattened index
mid, the corresponding row is mid / n and the column is mid % n, where n is the number of columns.
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int rows = matrix.length;
int columns = matrix[0].length;
int left = 0;
int right = rows * columns - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
int row = mid / columns;
int column = mid % columns;
if (matrix[row][column] == target) {
return true;
}
if (matrix[row][column] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return false;
}
}Complexity
The time complexity is O(log(m × n)), wherem is the number of rows and n is the number of columns. The space complexity is O(1).