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.

Have you met this question in a real interview?

Yes

Example

Consider the following matrix:

[
    [1, 3, 5, 7],
    [10, 11, 16, 20],
    [23, 30, 34, 50]
]

分析：这道题就是最基本的二分法，唯一的变化就是需要把原有的mid 拆分成横坐标和纵坐标

int midX = mid/n; int midY = mid%n;（n为二维矩阵的column的length）

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 || matrix.length == 0 || matrix[0].length == 0){
            return false;
        }

        int begin = 0;
        int m = matrix.length;
        int n = matrix[0].length;
        int end = m*n -1;

        while(begin + 1 < end){
            int mid = begin + (end - begin)/2;
            int midX = mid/n;
            int midY = mid%n;
            if(matrix[midX][midY]==target) 
            return true;

            if(matrix[midX][midY]<target){
                begin=mid;
            }else{
                end=mid;
            }

        }

        if(matrix[begin/n][begin%n]==target  || matrix[end/n][end%n]==target){
        return true;
        }

        return false;
    }

}