题目
编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
- 每行中的整数从左到右按升序排列。
- 每行的第一个整数大于前一行的最后一个整数。
示例 1：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 输出：true
示例 2：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13 输出：false
解题
方法一：二分查找 （二维转化为一维）
可以将二维展开成一维，然后就可以使用二分查找了
class Solution { public: bool searchMatrix(vector<vector<int>>& matrix, int target) { int m=matrix.size(),n=matrix[0].size(); int l=0,r=m*n-1; while(l<=r){ int mid=(l+r)>>1; int row=mid/n; int col=mid-row*n; if(matrix[row][col]==target){ return true; }else if(matrix[row][col]>target){ r=mid-1; }else{ l=mid+1; } } return false; } };
方法二：
从右上角出发，可以看成二叉搜索树
class Solution { public: bool searchMatrix(vector<vector<int>>& matrix, int target) { int m=matrix.size(),n=matrix[0].size(); int row=0,col=n-1; while(row<m&&col>=0){ if(matrix[row][col]<target){ row++; }else if(matrix[row][col]>target){ col--; }else{ return true; } } return false; } };
