二维数组中的查找
题目描述：
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
题目分析：
方法一：【暴力求解】
一开始如果没有头绪的话，显然暴力会是一种方法。
从第一行的第一个开始，与目标数进行比较，若相同，则数组含有目标数，停止遍历；若不相同，则继续向下遍历。如果遍历完所有的行和每行的所有数，仍没有找到目标数，则说明目标数不在该数组中。
这种方法时间复杂度是，实现起来很简单，就不写代码了。
方法二：【直接二分法】
到这里，我们会发现这种暴力解法并没有充分利用题目给出的已知条件——这个二维数组是有特点的：
- 每一行从左到右递增
- 每一列从上到下递增
也就是说这个二维数组每一行、每一列都是有序的。对于有序的一维数组的查找问题，最简单的方法是二分查找。
对于这个二维数组，我们也可以对其进行二分。具体是：
(利用循环)对每一行进行二分查找，时间复杂度为。因为一次二分查找时间复杂度为
，这里有n行，所以总的时间复杂度就是
。
// 直接二分
bool Find(int target,int A[][1000])
{
for(int i=0;i<n;i++)// n：总共有n行，即A.length
{
int low = 0;
int high= n-1;// n：每一行有n个数，即A[i].length
while(low<=high)
{
int mid=(low+high)/2;
if (target<A[i][mid])
high=mid-1;
else if(target>A[i][mid])
low=mid+1;
else
return true;
}
}
return false;
}
方法三：【规律法】
直接进行二分，仅利用到了列的有序性，也没有充分利用二维数组由上到下，由左到右递增的规律。
继续思考，我们会发现二维数组的四个顶点（想象为正方形）比较特殊。
假设从左下角开始遍历，如果当前值比 target 小则往右找，如果比 target 大则往上找，如果存在，必然可以找到目标数字target。
即选取左下角的元素 A[row] [col] 与 target 进行比较， 当target小于元素 A[row] [col] 时，那么 target 必定在元素 A 所在行的左边,让 col-- ；当 target 大于元素 A[row] [col] 时，那么 target 必定在元素 A 所在列的下边,让 row++ 。
当然我们也可以选取右上角进行如上类似的操作。
// 规律法
bool Find_1(int target, int A[][1000])
{
// 右上角
int row = 0;
int col = n - 1;// n：每一行有n个数，即A[i].length
while(row <= m - 1 && col >= 0)// m：总共有m行，即A.length
{
if(target == A[row][col])
return true;
else if(target > A[row][col])
row++;
else
col--;
}
return false;
}
方法四：【二分+规律】
将方法二和方法三进行结合：对每行每列都使用二分查找，此时的时间复杂度为其中n为行数，m为列数。
比如查找数字 9，首先使用二分查找选出一行，总共有 5 行，那么所以我们找出了第2行 为 基准行。
接下来对这一行（即第 2 行）又使用二分查找， 找出这一行（即第 2 行）中最后一个 比目标值小的值，这里是 6。
6 及其所在的行和列把这个矩形划分为 四 部分：
图 7
-
左上部分（图 7 灰色部分），包括所在行的左边部分和所在列的上边部分：这一部分是绝对不会有目标数字的。因为这部分数字肯定比 6 小，而 6 又是小于目标数字的，所以左上部分全部小于目标数字。也就是说这个区域的数字不需要再进行判断了。
-
右下部分（图 7 绿色部分），包括所在行的右边部分，但不包括所在列的下面部分， 这一部分也是绝对不会有目标数字的。因为这部分都比 6 右边的数字 11 大，而 11 又比目标数字 9 更大，所以右下部分全部都比目标数字大。也就是说这个区域的数字也不需要再进行判断了。
-
左下部分（图 7 蓝色部分），可能含有目标数字。
-
右上部分（图 7 棕色部分），可能含有目标数字。
这样，实际上筛选的区域就只剩下左下部分（图 7 蓝色部分）和 右上部分（图 7 棕色部分）这两块区域了，相比于方法三而言，使用这种解法平均情况下每一次查找，都可以把行和列的长度减少一半。
// 二分查找满足的列
int binarySearch(int A[1000], int target, int start, int end)
{
int i = (start + end) / 2;// 列的中间位置
if (A[i] == target || start > end)
{
return i;
}
else if (A[i] > target)
{
return binarySearch(A, target, start, i - 1);
}
else
{
return binarySearch(A, target, i + 1, end);
}
}
// 二分查找行，以及根据行列，与target进行比较
bool binarySearchIn2DArray(int A[][1000], int target, int start_row, int end_row, int start_col, int end_col)
{
if (start_row > end_row || start_col > end_col)
{
return false;
}
//首先，根据二分法找出中间行
int middle_row = (start_row + end_row) / 2;
//对该行进行二分查找
int middle_col = binarySearch(A[middle_row], target, start_col, end_col);
//找到的值位于 middle_row 行，middle_col 列
if (A[middle_row][middle_col] == target)
{
return true; // 如果找到则成功
}
//对剩余的两部分分别进行递归查找
return binarySearchIn2DArray(A, target, start_row, middle_row - 1, middle_col + 1, end_col)
|| binarySearchIn2DArray(A, target, middle_row + 1, end_row, start_col, middle_col);
}
//
bool Find_2(int target, int A[][1000])
{
// 特殊情况处理
if (A == NULL || n == 0 || m == 0)
{
return false;
}
int row = n - 1;
int col = m - 1;
// 如果目标值小于最小值 或者 目标值大于最大值，那肯定不存在
if (A[0][0] > target || A[row][col] < target)
{
return false;
}
return binarySearchIn2DArray(A, target, 0, row, 0, col);
}
附上一份完整的Cpp代码：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,t;
int base[1000][1000];
// 直接二分
bool Find(int target,int A[][1000])
{
for(int i=0;i<m;i++)// m：总共有m行，即A.length
{
int low = 0;
int high= n-1;// n：每一行有n个数，即A[i].length
while(low<=high)
{
int mid=(low+high)/2;
if (target<A[i][mid])
high=mid-1;
else if(target>A[i][mid])
low=mid+1;
else
return true;
}
}
return false;
}
// 规律法
bool Find_1(int target, int A[][1000])
{
// 右上角
int row = 0;
int col = n - 1;// n：每一行有n个数，即A[i].length
while(row <= m - 1 && col >= 0)// m：总共有m行，即A.length
{
if(target == A[row][col])
return true;
else if(target > A[row][col])
row++;
else
col--;
}
return false;
}
// 二分查找满足的列
int binarySearch(int A[1000], int target, int start, int end)
{
int i = (start + end) / 2;// 列的中间位置
if (A[i] == target || start > end)
{
return i;
}
else if (A[i] > target)
{
return binarySearch(A, target, start, i - 1);
}
else
{
return binarySearch(A, target, i + 1, end);
}
}
// 二分查找行，以及根据行列，与target进行比较
bool binarySearchIn2DArray(int A[][1000], int target, int start_row, int end_row, int start_col, int end_col)
{
if (start_row > end_row || start_col > end_col)
{
return false;
}
//首先，根据二分法找出中间行
int middle_row = (start_row + end_row) / 2;
//对该行进行二分查找
int middle_col = binarySearch(A[middle_row], target, start_col, end_col);
//找到的值位于 middle_row 行，middle_col 列
if (A[middle_row][middle_col] == target)
{
return true; // 如果找到则成功
}
//对剩余的两部分分别进行递归查找
return binarySearchIn2DArray(A, target, start_row, middle_row - 1, middle_col + 1, end_col)
|| binarySearchIn2DArray(A, target, middle_row + 1, end_row, start_col, middle_col);
}
//
bool Find_2(int target, int A[][1000])
{
// 特殊情况处理
if (A == NULL || n == 0 || m == 0)
{
return false;
}
int row = n - 1;
int col = m - 1;
// 如果目标值小于最小值 或者 目标值大于最大值，那肯定不存在
if (A[0][0] > target || A[row][col] < target)
{
return false;
}
return binarySearchIn2DArray(A, target, 0, row, 0, col);
}
int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
// 二维数组：base[n][m]；目标数：t
while(~scanf("%d%d%d",&n,&m,&t))
{
int index;
memset(base,0,sizeof(base));
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
scanf("%d",&base[i][j]);
}
}
/*
// 输出二维数组
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
printf("%d ",base[i][j]);
}
puts("");
}
*/
bool res=Find(t,base);// 直接二分
bool res_1=Find(t,base);// 规律
bool res_2=Find(t,base);// 二分+规律
if(res)printf("直接二分：Yes\n");
else printf("直接二分：No\n");
if(res_1)printf("规律：Yes\n");
else printf("规律：No\n");
if(res_2)printf("二分+规律：Yes\n");
else printf("二分+规律：No\n");
}
//fclose(stdin);
//fclose(stdout);
}
输入
运行结果
写在最后：
参考资料：
- 公众号：五分钟学算法
- 文章：https://mp.weixin.qq.com/s/R8NJNaJH0JO08NgTmqdEMQ
一直关注着这个五分钟学算法公众号，此文章仅作为学习笔记，侵删！！！
如有错误，还望指正。
网友评论