Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
- Integers in each row are sorted from left to right.
- The first integer of each row is greater than the last integer of the previous row.
For example,
Consider the following matrix:
[ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ]Given target = 3, return true.
O(M+N)
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix==null||matrix.length==0) {
return false;
}
int rows = matrix.length;
int columns = matrix[0].length;
int left = 0;
int right = columns-1;
while (left<rows && right>=0) {
if (matrix[left][right]==target) {
return true;
} else if (matrix[left][right]<target) {
left = left + 1;
} else {
right = right - 1;
}
}
return false;
}
O(logN)
From the example above:
position: 0 1 2 3 4 5 6 7 8 9 10 11
values: 1 3 5 7 10 11 16 20 23 30 34 50
row: 0 0 0 0 1 1 1 1 2 2 2 2
column: 0 1 2 3 0 1 2 3 0 1 2 3
rows = 3, columns =4
we can calculate left =0, right=rows*collumns-1 and middle is 0+(11-0)/2 = 5
which is [1,1] = 11
x = 5/4 = 1
y = 5%4 = 1
so we know X = middle/columns and Y = middle%columns.
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix==null||matrix.length==0||matrix[0].length==0) {
return false;
}
int rows = matrix.length;
int columns = matrix[0].length;
int start = 0;
int end = rows*columns-1;
while (start<=end) {
int middle = start + (end-start)/2;
int middleX = middle/columns;
int middleY = middle%columns;
if (matrix[middleX][middleY]==target) {
return true;
} else if (matrix[middleX][middleY]>target) {
end = middle-1;
} else {
start = middle+1;
}
}
return false;
}