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.

题意：给定一个矩阵，每一行都是递增的，每行行首大于上一行行尾。在矩阵中找一个元素，是否能找到？

思路：首先，自己的思路是先找到元素所在的行，可以通过判断元素和行首行尾的关系确定；然后，在找到的行内用二分法搜索，时间复杂度row + log(col)。

public boolean searchMatrix(int[][] matrix, int target) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
        return false;
    }

    int m = matrix.length, n = matrix[0].length;
    int row = -1;
    for (int i = 0; i < m; i++) {
        if (target >= matrix[i][0] && target <= matrix[i][n-1]) {
            row = i;
            break;
        }
    }
    if (row == -1) {
        return false;
    }

    int left = 0, right = n - 1;
    while (left + 1 < right) {
        int mid = left + (right - left) / 2;
        if (matrix[row][mid] == target) {
            return true;
        } else if (matrix[row][mid] < target) {
            left = mid;
        } else {
            right = mid;
        }
    }

    if (matrix[row][left] == target || matrix[row][right] == target) {
        return true;
    }

    return false;
}

查看discuss更好的思路。其实根绝这个二维矩阵的特性，这个二维矩阵可以看做一个一维递增的数组，所以可以直接在这个矩阵中用二分搜索。

public boolean searchMatrix(int[][] matrix, int target) {

    int row_num = matrix.length;
    int col_num = matrix[0].length;

    int begin = 0, end = row_num * col_num - 1;

    while(begin <= end){
        int mid = (begin + end) / 2;
        int mid_value = matrix[mid/col_num][mid%col_num];

        if( mid_value == target){
            return true;

        }else if(mid_value < target){
            //Should move a bit further, otherwise dead loop.
            begin = mid+1;
        }else{
            end = mid-1;
        }
    }

    return false;
}