public class Solution {
/**
 * @param matrix, a list of lists of integers
 * @param target, an integer
 * @return a boolean, indicate whether matrix contains target
 */
public boolean searchMatrix(int[][] matrix, int target) {
    // write your code here
    if (matrix == null) return false;
    int row = matrix.length;
    if (row == 0) return false;
    int column = matrix[0].length;
    int start = 0;
    int end = row - 1;
    while (start + 1 < end) {
        int mid = start + (end - start) / 2;
        if (matrix[mid][0] == target) start = mid;
        else if (matrix[mid][0] > target) end = mid;
        else start = mid;
    }
    int numLine = 0;
    int low = 0;
    int high = column - 1;
    if (matrix[end][0] <= target) numLine = end;
    else if (matrix[start][0] <= target) numLine = start;
    else return false;
    while (low + 1 < high) {
        int mid = low + (high - low) / 2;
        if (matrix[numLine][mid] == target) return true;
        else if (matrix[numLine][mid] > target) high = mid;
        else  low = mid;
    }
    if (matrix[numLine][low] == target || matrix[numLine][high] == target)
        return true;
    else return false;
}
}

public class Solution {
/**
 * @param matrix, a list of lists of integers
 * @param target, an integer
 * @return a boolean, indicate whether matrix contains target
 */
    public boolean searchMatrix(int[][] matrix, int target) {
    // write your code here
    if (matrix == null) return false;
    int row = matrix.length;
    if (row == 0) return false;
    int column = matrix[0].length;
    int start = 0;
    int end = row * column - 1;
    while (start + 1 < end) {
        int mid = start + (end - start) / 2;
        int m = mid / column;
        int n = mid % column;
        if (matrix[m][n] == target) return true;
        else if (matrix[m][n] > target) end = mid;
        else start = mid;
    }
    if (matrix[start / column][start % column] == target ||
        matrix[end / column][end % column] == target ) return true;
    return false;
}
}