本文共 1798 字，大约阅读时间需要 5 分钟。

思想：

从左边用二分查找，找到第一个大于目标的行。如果没有大于就返回最后一个小于或者等于的行。然后在行内再用二分查找看看有没有对应的数。

public class Solution {
       public boolean searchMatrix(int[][] matrix, int target) {        int latRow=getRow(matrix, target, 0, matrix.length-1);        for(int i=0;i<=latRow;i++)        {            if(Arrays.binarySearch(matrix[i], target)>=0)            {                return true;            }        }        return false;    }     public int getRow(int [][] matrix,int target,int begin,int end)    {        if(begin==end)        {            return end;        }        if(begin>end)        {            return begin;        }        int middle=(begin+end)/2;        if(matrix[middle][0]<=target)        {            return getRow(matrix, target, middle+1, end);        }        else        {            return getRow(matrix, target, begin, middle-1);        }    }}

还有一个别人的思路

just like searching a sorted an array; find the middle element and recursively search the rest 3/4 matrix; a decrease (devide) and conquer solution;

The time complexity is T(mn) = T(1/4 mn) + T(1/2 m*n) + 1

public boolean searchMatrix(int[][] matrix, int target) {    return(searchMatrixHelper(matrix, 0, 0, matrix.length-1, matrix[0].length-1, target));}private boolean searchMatrixHelper (int[][] matrix, int i, int j, int i_, int j_, int target){    if(i > i_ || j> j_){        return false;    }    int midRow= (i+i_)/2; int midCol=(j+j_)/2;    if(matrix[midRow][midCol] == target){        return true;    }else if(matrix[midRow][midCol] > target){        return (searchMatrixHelper(matrix, i ,j, i_, midCol-1, target) || searchMatrixHelper(matrix, i, midCol, midRow-1, j_, target));    }else{        return (searchMatrixHelper(matrix, midRow+1 ,j, i_, j_, target) || searchMatrixHelper(matrix, i, midCol+1, midRow, j_, target));    }}

转载地址：http://sbuvb.baihongyu.com/