public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0) {
return false;
}
int row, column;
//find row index
int start = 0;
int end = matrix.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (target == matrix[mid][0]) {
return true;
} else if (target < matrix[mid][0]) {
end = mid;
} else {
start = mid;
}
}
if (target == matrix[start][0] || target == matrix[end][0]) {
return true;
} else if (target > matrix[start][0] && target < matrix[end][0]) {
row = start;
} else if (target > matrix[end][0]) {
row = end;
} else {
return false;
}
//find column
start = 0;
end = matrix[row].length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (target == matrix[row][mid]) {
return true;
} else if (target < matrix[row][mid]) {
end = mid;
} else {
start = mid;
}
}
if (target == matrix[row][start]) {
return true;
}
if (target == matrix[row][end]) {
return true;
}
return false;
}
}