题目搬运:
例如下面的二维数组,每行每列都是递增,如果在数组中查找数字7,则返回true;如果查找5,因为5不存在,则返回false:
1 2 8 9
2 4 9 12
4 7 10 13
6 8 11 15
思路
既然是查找,有序列表一般最有效率的查找是二分查找,然后二维数组的所谓分界点,其实就是角落的点,那么选择哪个角呢?
比如右上角,所有同行的值,都比他小,所有同列的值,都比他大;比如左下角,所有同列值,都比他小,所有同行的值,都比他大;似乎想到了什么?对,快速排序,有了不同方向的比较,就有了递归。
假设选取右上角,如果刚好是所查找的值,返回ture;如果不是,比较查找的值,如果比右上角的值小,例如7,则删除最后一列,继续比较右上角的值,即8;如果比右上角的值大,例如11,则删除最上一行,继续比较右上角的值,即12;查找到即递归结束,或者遍历完直到左下角。
解决
以C艹为例:
using namespace std;
bool Find(int arr[MAXLEN][MAXLEN],int num,int x,int y,int nLen)
//MAXLEN最大维度 nLen数组维度 num待查找值
{
if (x > nLen - 1 || y < 0)
{
return false;
}
if (arr[x][y] == num)
{
cout<<"x = "<<x<<" y = "<<y<<endl;
return true;
}
else if (arr[x][y] > num)
{
return Find(arr,num,x,y - 1,nLen);
}
else
{
return Find(arr,num,x + 1,y,nLen);
}
}