有序二维数组中的查找

题目：在一个二维数组中，每一行都按照从左到右递增的顺序排列，每一列都按照从上到下递增的顺序排列。输入这样一个二维数组和一个整数，判断数组中是否含有该整数。

目前创新互联建站已为上千多家的企业提供了网站建设、域名、虚拟主机、成都网站托管、企业网站设计、太仆寺网站维护等服务，公司将坚持客户导向、应用为本的策略，正道将秉承"和谐、参与、激情"的文化，与客户和合作伙伴齐心协力一起成长，共同发展。

思路：首先看到这样一个题目我们先分析题目，把二维数组在纸上画成一个矩形。列如：1 2 8 9

                                       2 4 9 12  

                                       4 7 10 13     

                                       6 8 11 15

然后从数组中选取一个数字7。分三种情况来分析查找过程：当选取的数字跟要查找的数字相等时，结束。当选取的数字小于要查找的数字时，要查找的数字应该在当前选取数字的右边或者下边。当选取的数字大于要查找的数字时，要查找的数字应该在当前选取数字的左边或者上边。

这种情况有可能会出现重叠区域，代码不太容易实现。

我们可以换种角度思考，减少查找的范围，我们每次都以右上角的数字作为标准进行比较，当查找的数字小于右上角的数字时，剔除该数字所在的这一列。当查找的数字大于右上角的数字时，剔除该数字所在的这一行。慢慢的减少查找的范围，最终找到该数字。

代码实现如下：

#include<iostream>
using namespace std;
bool Find(int (*arr)[4],int rows,int cols,int num)
{
	if(arr!=NULL && rows>0 && cols>0)
	{
		int row=0;
		int col=cols-1;
		while(row<rows && col>=0)
		{
			if(arr[row][col]==num)
				return true;
			else if(arr[row][col]>num)
				col--;
			else
				row++;
		}
		return false;
	}
}
int main()
{
	int arr[][4]={1,2,8,9,2,4,9,12,4,7,10,13,6,8,11,15};
	bool ret=Find(arr,4,4,7);
	cout<<ret<<endl;
	return 0;
}

网站名称：有序二维数组中的查找
本文URL：https://www.cdcxhl.com/article44/posjhe.html

成都网站建设公司_创新互联，为您提供网站策划、自适应网站、网站建设、定制网站、面包屑导航、移动网站建设

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联