题目：

写出一个高效的算法来搜索 m × n矩阵中的值。

这个矩阵具有以下特性：

• 每行中的整数从左到右是排序的。
• 每行的第一个数大于上一行的最后一个整数。

样例

考虑下列矩阵：

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

给出 target = 3，返回 true

挑战

O(log(n) + log(m)) 时间复杂度

解题：

更新730

直接二分查找

public boolean searchMatrix(int[][] A, int target) {        // write your code here        if(A == null || A.length == 0 || A[0].length ==0)            return false;        int row = A.length;        int col = A[0].length;        int len = row * col;        int left = 0;        int right = len-1 ;//         while(left <= right){            int mid = left + (right - left)/2;            int x = A[mid/col][mid%col];            if(x==target){                return true;            }else if(x>target){                right = mid-1;            }else{                left = mid+1;            }        }        return false;    }

 

1.最简单的方法就是遍历整个矩阵，时间复杂度：O(log(mn)),这个应该等于O(long(n)+log(m))

2.题目给的矩阵是有序矩阵，先按照最后一列二分查找，确定列，再二分确定行，时间复杂度O(log(m)) + O(log(n)),哦，哦，哦，题目的挑战可能是搞错了。。。

1.暴力

Java程序：

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 m  = matrix.length;        if(m==0)            return false;        int n = matrix[0].length;        for(int i=0;i

 总耗时: 1571 ms

Python程序：

class Solution:    """    @param matrix, a list of lists of integers    @param target, an integer    @return a boolean, indicate whether matrix contains target    """    def searchMatrix(self, matrix, target):        # write your code here        if matrix==None:            return False        m = len(matrix)        if m==0:            return False        n = len(matrix[0])        for i in range(m):            for j in range(n):                if matrix[i][j]==target:                    return True        return False

总耗时: 260 ms

2.二分法

利用二分思想程序，先求所在的行，再求所在的列，搞了好久，边界错了好多次。。。

Java程序：

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 nrow  = matrix.length;        if(nrow==0)            return false;        int ncol = matrix[0].length;        // 行 nrow        //列 ncol        int row = rowbinSearch(matrix,0,nrow-1,ncol,target);        int col = colbinSearch(matrix,0,ncol-1,row,target);        if(col!=-1)            return true;        return false;    }    // 找出所在的行    private int rowbinSearch(int[][] matrix,int left,int right,int ncol,int target){        //矩阵matrix ，二分的两个界：left、right，矩阵的最后一列ncol,目标值target        int median = (left + right)/2;        int row = median;        if(left==right)            return left;        if(matrix[left][ncol-1]<=target && matrix[left+1][ncol-1]>target)            return left;        if(matrix[median][ncol-1]>= target && matrix[median][0]<=target)            return median;        if(matrix[median][ncol-1]
         
          right)            return -1;        if(left==right && matrix[row][left]!=target)            return -1;        if(matrix[row][median]==target)            return median;        if(matrix[row][median]
         

总耗时: 2246 ms

3.暴力2.0

中看到的，给的Java程序利用二分法，但是没有用递归，给的Python程序，没有明显的用到矩阵变量，但是通过商和余数确定所在的行和列

Python程序：

class Solution:    """    @param matrix, a list of lists of integers    @param target, an integer    @return a boolean, indicate whether matrix contains target    """    def searchMatrix(self, matrix, target):        # write your code here        if len(matrix)==0:            return False        n,m=len(matrix),len(matrix[0])        start,end = 0,n*m-1        while start+1< end:            mid = (start + end)/2            x,y = mid/m,mid%m            if matrix[x][y]

总耗时: 261 ms

更新

可每次去除一行或者一列，这样划分的形式解题

时间复杂度O(M+N)

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 row = 0;        int col = matrix[0].length-1;        return searchMatrix(matrix,row,col,target);    }    // 右上角开始是找    public boolean searchMatrix(int[][] mat,int row,int col,int target){        if(row<0 || row>= mat.length || col<0 || col>mat[0].length)            return false;        if(mat[row][col] == target)            return true;        else if(mat[row][col] < target)            return searchMatrix(mat,row+1,col,target);        else            return searchMatrix(mat,row,col-1,target);    }}

该成递归形式

注意下面的两个while循环

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 row = 0;        int col = matrix[0].length-1;    // 注意下面两个while 循环 row  col 都要判断的        while(row< matrix.length&& col>=0){            while(row< matrix.length&& col>=0){                if (matrix[row][col] == target){                    return true;                }else if(matrix[row][col] > target){                    col--;                }else{                    row++;                }            }        }        return false;    }}