tags:
- 数组
- 查找
- 二分查找
题目描述
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
题目链接：剑指offer1 二维数组中的查找
C++解题
思路1：遍历二维vector
代码如下：
class Solution
{
public:
bool Find(int target, vector<vector<int> > array)
{
int i=0,j=0;
for(i=0;i<array.size();++i) //注意这里对于二维vector的操作
{
for(j=0;j<array[0].size();++j)
{
if(target==array[i][j])
return true;
}
}
return false;
}
};
复杂度分析：行列均遍历一遍，复杂度为
思路2：遍历列，对行进行二分查找
代码如下：
class Solution
{
public:
bool Find(int target, vector<vector<int> > array)
{
int i=array.size();
for(i=0;i<array.size();++i)
{
int low=0;
int high=array[i].size()-1;
int mid=0;
while(low<=high) //注意二分查找终止条件 <=
{
mid=(low+high)/2; //注意这里需要更新mid，不用严格考虑奇偶
if(target==array[i][mid])
return true;
else if(target<array[i][mid])
high=mid-1;
else
low=mid+1;
}
}
return false;
}
};
复杂度分析：列遍历一遍，行二分查找，复杂度为
思路3：根据数据信息，选择从左下角/右上角开始查找
思路描述：因为每行从左到右依次变大，每列从上到下依次变大。以从右上角出发为例，若target大于该值则向下查询，若target小于该值则向左查询。因为比该值大的只可能在下方或下左方，比该值小的只可能在左方或者左下方，而从右上方开始搜索，最坏的情况为target不在数组中，此时需要搜索的次数是2n次，即时间复杂度为
代码如下：
class Solution
{
public:
bool Find(int target, vector<vector<int> > array)
{
// 从右上角开始向左向下搜索
int row=0;
int col=array[0].size()-1; // 注意这里是n-1
while(col>=0&&row<array.size())
{
if(target==array[row][col])
return true;
else if(target>array[row][col]) // target大于当前位置，向下搜索
row=row+1;
else // target小于当前位置，向左搜索
col=col-1;
}
return false;
}
};
复杂度分析：特殊查找类型，相当于只把某1行和某1列进行了查找，复杂度为
知识点总结
- C++ STL的vector操作
- 二分查找mid的设置和更新，可以用while也可以用递归，记住边界条件
- 思路2、3中的搜索方法，值得记住
