剑指 Offer 04. 二维数组中的查找
在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
示例:
现有矩阵 matrix 如下：
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。
给定 target = 20，返回 false。
限制：
0 <= n <= 1000
0 <= m <= 1000
我的解法：二分法
class Solution {
int m,n;
public:
bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
//输入合法性判断
if(matrix.size() == 0 )//if(matrix[0].size()==0)不妥，matrix为空，matrix[0]出错
{
return false;
}
m = matrix.size(); n = matrix[0].size();
//逐行二分遍历查找
for(int j = 0; j < m; j++)
{
//当前行二分查找
int low = 0;
int high = n - 1;
int mid = (low + high) / 2;
while (low <= high)
{
if (matrix[j][mid] == target)
{
return true;
}
else if (target < matrix[j][mid])
{
high = mid-1;
}
else
{
low = mid + 1;
}
mid= (low + high) / 2;
}
}
return false;//所有行找不到，返回无
}
};
class Solution {
int m , n;
public:
bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
//输入合法性判断
m = matrix.size();
if( m == 0 )
{
return false;
}
n = matrix[0].size();//必须放在m==0条件判断之后，放在matrix为空出错
//逐行二分遍历查找
for(int j = 0; j < m; ++j)
{
//当前行二分查找
if(binaryFind(matrix, j, target))
return true;
}
return false;//所有行找不到，返回无
}
bool binaryFind(vector<vector<int>>& matrix, int j, int target)
{
int low = 0;
int high = n;
while (low < high)
{
int mid = (low + high) / 2;
if (matrix[j][mid] == target)
{
return true;
}
else if (target < matrix[j][mid])
{
high = mid;
}
else if(target > matrix[j][mid])//这个直接else不加if条件，可能会慢4ms
{
low = mid + 1;
}
}
return false;
}
};
爬坑记录：
Line 1033: Char 9: runtime error: reference binding to null pointer of type 'std::vector>' (stl_vector.h) SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_vector.h:1043:9
该问题是matrix为空引起的索引越界错误。
即：if(matrix[0].size()==0)不妥，matrix为空，matrix[0]出错
