Array search algorithm with row elements increasing from small to large and column elements increasing from small to large

Question: In a two-dimensional array, each row is sorted in increasing order from left to right, and each column is sorted in increasing order from top to bottom. Please complete a function, input such a two-dimensional array and an integer, and determine whether the array contains the integer.

Test points: This question is mainly about making good use of the two conditions given, row increment and column increment, to exclude data that is definitely inappropriate, and to reduce the data to be traversed as much as possible.

Array examples are as follows:

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

When solving a complex problem, the most effective way is to start with the analysis from the specific problem.

It can be seen from observation that

1. If the beginning of the column is larger than the number you want to find, then the number you want to find cannot be in that column, and you can directly prune that column;

The results are as follows:

1	2
2	4
4	7
6	8

2. After passing the pruning column, you can Found that the number at the end of the line If it is less than the number you are looking for, then the number you are looking for is definitely not in that row;

The result is as follows:

4	7
6	8

3. Like this Just cut the data into the smallest possible amount, and then traverse and search the data. That's it.

The code is as follows:

<?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.&#39;,&#39;;
			//如果查找的数大于数组中的所有元素，那么就遍历完所有的行后退出
			//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));

Copyright statement: This article is an original article by the blogger and may not be reproduced without the blogger's permission.

The above introduces the array search algorithm in which the row elements increase from small to large and the column elements increase from small to large, including the relevant content. I hope it will be helpful to friends who are interested in PHP tutorials.