力扣74、搜索二维矩阵

1、直接循环（4ms,76%;9.3MB,31%）

时间复杂度：O（n）：最坏情况要遍历整个数组

空间复杂度：O（1）

bool searchMatrix(vectorint>>& matrix, int target) {
        if(matrix.empty())
        return false;
        //m为二维数组的行数，n为二维数组的列数
        int m=matrix.size();
        int n=matrix[0].size();
        for(int i=0;i)
        for(int j=0;j){
            if(matrix[i][j]==target)
            return true;
        }
        return false;
    }

2、用两次二分（4ms,76%;9.2MB,84%）

时间复杂度：O（log mn）：m、n分别为矩阵行数、列数

空间复杂度：O（1）

 1 bool searchMatrix(vectorint>>& matrix, int target) {
 2         //m为矩阵的行数，n为矩阵的列数
 3         int m=matrix.size();
 4         int n=matrix[0].size();
 5          if(matrix.empty())
 6         return false;
 7         int left=0,right=m-1;
 8         int mid=0;
 9         int tar=-1;
10         //第一次二分，用于查找目标值所在的行
11         while(left<=right){
12             mid=(left+right)/2;
13             //if()成立说明目标值可能在该行上
14             if(target>=matrix[mid][0]&&target<=matrix[mid][n-1]){
15                 //用tar保存该行的下标，防止和后面的mid弄混
16                 tar=mid;
17                 break;
18             }
19             else if(target0])
20             right=mid-1;
21             else
22             left=mid+1;
23         }
24         //第二次二分，用于查找该行是否有目标值
25         if(tar!=-1){
26             left=0,right=n-1;
27             while(left<=right){
28                 mid=(left+right)/2;
29                 if(matrix[tar][mid]==target)
30                 return true;
31                 else if(matrix[tar][mid]<target)
32                 left=mid+1;
33                 else
34                 right=mid-1;
35             }
36         }
37         return false;
38     }

3、用树来做（0ms,100%;9.2MB,69%）

时间复杂度：O（m+n）：m、n分别为矩阵行数、列数

空间复杂度：O（1）

 1  bool searchMatrix(vectorint>>& matrix, int target) {
 2         int m=matrix.size();
 3         int n=matrix[0].size();
 4         //判断条件这里注意要&&，整个过程利用了矩阵的有序性
 5         //从首行的末尾开始比较，因为其左边的比它小，下面的比它大
 6         for(int i=0,j=n-1;i=0;){
 7             if(matrix[i][j]==target)
 8             return true;
 9             //目前偏小则往下面跳
10             else if(matrix[i][j]<target)
11             i++;
12             //目前偏大则往左边跳
13             else
14             j--;
15         }
16         return false;
17     }