编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-a-2d-matrix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
执行用时 :4 ms, 在所有 C++ 提交中击败了99.23%的用户
内存消耗 :7.7 MB, 在所有 C++ 提交中击败了100.00%的用户
总共用了四小时才做出来。题目本身不难，奈何自己将思路转换成代码的编程能力不过关，边界情况考虑也不充分。
昨晚俩小时就想，这题就是一个二分的题呀，如果知道L(lrow,lcol)和R(rrow,rcol)能换算出mid(mrow,mcol)就解决了呀，然后就一直，，没设计出来，嗯最后还是选择去睡觉了。
今早就突然想到，可以先在矩阵的行上二分查找，然后继续在列上二分。思路很简单，然而边界一大堆。
首先是行数的确定，不同于普通二分，也不同于寻找左右边界，这个行必须得等于mid，如果等于mid+1就可能把目标值所在行跳过了。
但是随之而来又有一个问题，行=mid，会有循环一直进行的情况，行=mid，然后还是行=mid，一直跳不出来。
最后还要保证访问的下标不越界。
第二种思路代码如下：
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if (matrix.size() == 0)
return false;
int topRow = 0;
int downRow = matrix.size();
while (topRow != downRow - 1)//防止 topRow一直等于mid，死循环
{
int mid = (topRow + downRow) / 2;
if (matrix[mid][0]<target)
topRow = mid; //不能用topRow = mid+1，防止跳过目标值所在行
else if (matrix[mid][0]>target)
downRow = mid;
else
return true;
}
//topRow和downRow 相差1，解决目标值所在行，要防止downRow 一直没变，始终等于matrix.size() ，那下面寻找所在列，就会超出索引
int atRow = (downRow<matrix.size() && matrix[downRow][0]<target) ? downRow : topRow;
int leftCol = 0;
int rigCol = matrix[0].size();
while (leftCol<rigCol)
{
int mid = (leftCol + rigCol) / 2;
if (matrix[atRow][mid]<target)
leftCol = mid + 1;
else if (matrix[atRow][mid]>target)
rigCol = mid;
else
return true;
}
return false;
}
};
第一种思路
自己把第二种思路死磕实现之后，觉得是不是自己想的太复杂了，于是看了看官方的题解[1]，感觉思路很妙。
第一种思路难在，是知道L和R，怎么算mid。这么想就很难解决了。
现在直接把输入的mxn二维矩阵可以视为长度为mxn的一维有序数组。那么只需要知道一维数组的元素mIndex和二维矩阵元素m[mrow,mcol]的对应关系。
mrow= mIndex / matrix[0].size();
mcol= mIndex % matrix[0].size();
知道这个对于关系，就可以套用二分查找啦。
执行用时 :8 ms, 在所有 C++ 提交中击败了87.06%的用户
内存消耗 :7.7MB, 在所有 C++ 提交中击败了100.00%的用户
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int row = matrix.size();
if (row == 0) return false;
int col = matrix[0].size();
int left = 0, right = row * col;
int mIndex=0, m=0;//初始化是一个很好的习惯 mIndex是一维数组的元素位置，m是二维矩阵对应的元素
while (left < right) {
mIndex = (left + right) / 2;
m= matrix[mIndex / col][mIndex % col];
if (m < target)
left = mIndex+1;
else if(m > target)
right =mIndex;
else
return true;
}
return false;
}
};
自己死磕的比官方还要快一些，心里终于平衡一些，没白费四小时哈哈。
另外推荐一个阐述二分查找细节的不错的博客。
