行元素从小到大递增，列元素从小到大递增的数组查找算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了行元素从小到大递增，列元素从小到大递增的数组查找算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1650字，纯文字阅读大概需要3分钟。

内容图文

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

考点：这道题主要是要利用好所给的两个条件，行递增和列递增，将肯定不合适的数据排除在外，将要遍历的数据尽可能的减少。

数组例子如下：

1	2	8	9
2	4	9	12
4	7	10	13
6	8	11	15

解决一个复杂的问题时，最有效的办法就是从具体的问题入手分析。

通过观察可知，

1.列最开头如果大于要查找的数，那么要查找的数不可能在那一列，可以直接剪枝掉那一列；

结果如下：

1	2
2	4
4	7
6	8

2.通过剪枝列之后，可以发现，行最末尾的数如果小于要查找的数，那么要查找的数肯定也不在那一行；

结果如下：

4	7
6	8

3.这样数据就剪成最少的可能的数量，然后再对这些数据进行遍历查找，就可以了。

代码如下：

<?php
/*
$data  数组
$number 查找的数
$rows 数组的行数
$columns 数组的列数
*/
function inArray($data,$number,$rows,$columns)
{
	$row=0;
	$column=$columns-1;
	$first=true;
	while($row<$rows&&$column>=0)
	{
		if($data[$row][$column]>$number&&$first)
		{
			$column--;
			//echo $column.',';
		}
		if($data[$row][$column]<$number)
		{
			$first=false;
			$row++;
			//echo $row.',';
			//如果查找的数大于数组中的所有元素，那么就遍历完所有的行后退出
			//continue是防止这种情况的出现，会和第四个条件冲突
			continue;
		}
		if($data[$row][$column]==$number)
		{
			return true;
		}
		if($data[$row][$column]>$number&&!$first)
		{
			break;
		}
	}

	for($i=$row;$i<$rows;$i++)
	{
		for($j=0;$j<$column;$j++)
		{
			if($data[$i][$j]==$number)
			{
				return true;
			}
		}
	}
	return false;
}

$a=array(array(1,2,8,9),array(2,4,9,12),array(4,7,10,13),array(6,8,11,15));
var_dump(inArray($a,7,4,4));
var_dump(inArray($a,101,4,4));

版权声明：本文为博主原创文章，未经博主允许不得转载。

以上就介绍了行元素从小到大递增，列元素从小到大递增的数组查找算法，包括了方面的内容，希望对PHP教程有兴趣的朋友有所帮助。

内容总结

以上是互联网集市为您收集整理的行元素从小到大递增，列元素从小到大递增的数组查找算法全部内容，希望文章能够帮你解决行元素从小到大递增，列元素从小到大递增的数组查找算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---