BiruLyu
7/26/2017 - 12:07 AM

74. Search a 2D Matrix(#).java

``````public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
return false;
}
int start = 0;
int end = matrix.length - 1;

while(start <= end){
int mid = start + (end - start) / 2;
if(matrix[mid][0] == target){
return true;
}
else if(matrix[mid][0] < target){
start = mid + 1;
}
else{
end = mid - 1;
}
}

int targetRow = end;
if(targetRow < 0){
return false;
}

start = 0;
end = matrix[0].length - 1;

while(start <= end){
int mid = start + (end - start) / 2;
if(matrix[targetRow][mid] == target){
return true;
}
else if(matrix[targetRow][mid] > target){
end = mid - 1;
}
else{
start = mid + 1;
}
}

return false;
}
}``````
``````public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length < 1 || matrix[0].length < 1) return false;
int m = matrix.length;
int n = matrix[0].length;
int l = 0;
int r = m * n - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
int cur = matrix[mid / n][mid % n];
if (cur == target) return true;
else if (cur > target) {
r = mid - 1;
} else {
l = mid + 1;
}
}
return false;
}
}``````