【解题报告】【lintcode28】Search a 2D Matrix

题意

写出一个高效的算法来搜索 m × n矩阵中的值。 这个矩阵具有以下特性： 每行中的整数从左到右是排序的。 每行的第一个数大于上一行的最后一个整数。 性能要求，时间复杂度O（logm+logn）

解答

两次二分，第一次确定所在行，第二次确定所在列

代码

    public boolean searchMatrix(int[][] matrix, int target) {
        // write your code here
        int m,n,mt = -1,nt = -1;
        if(matrix == null|| matrix.length == 0)return false;
        m = matrix.length;
        n = matrix[0].length;
     
        int h,l,mid;
        l = 0;
        h = m -1;
        while(l <= h&&h >= 0&&l < m){
            mid = (l + h)/2;
            if(matrix[mid][0] > target){
                h = mid - 1;
            }else if(matrix[mid][0] < target&&mid+1<m&&matrix[mid+1][0] < target){
                l = mid + 1;
            }else{
                mt =  mid;
                break;
            }
        }
        if(mt < 0)return false;
        l = 0;
        h = n - 1;
        while(l <= h&&h >= 0&&l < n){
            mid = (l + h)/2;
            if(matrix[mt][mid] > target){
                h = mid - 1;
            }else if(matrix[mt][mid] < target){
                l = mid + 1;
            }else{
                nt =  mid;
                break;
            }
        }
        if (nt < 0)return false;
        return true;
    }