行要素が小さいものから大きいものに増加し、列要素が小さいものから大きいものに増加する配列検索アルゴリズム

質問: 2 次元配列では、各行は左から右に昇順に並べ替えられ、各列は上から下に昇順に並べ替えられます。関数を完成させ、二次元配列と整数を入力し、配列に整数が含まれているかどうかを判定してください。

テストポイント: この質問は主に、与えられた 2 つの条件、行増分と列増分をうまく利用して、明らかに不適切なデータを除外し、走査するデータを可能な限り減らすことに関するものです。

配列の例は次のとおりです: 9

12

4 71013681115 複雑な問題を解決する場合、最も効果的な方法は、具体的な問題から分析を始めることです。 観察すると、1. 列の先頭が検索したい数値より大きい場合、検索したい数値はその列には存在せず、その列を直接削除できます。 結果は次のとおりです: 1224

4

7

6

82.列を枝刈りした後、行末の数値が探している数値より小さいことがわかります。探している数値は間違いなくその行にありません。結果は次のようになります。 : 4768 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.&#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));

著作権表示: この記事はブロガーによるオリジナルの記事であり、ブロガーの許可なく複製することはできません。

以上、行要素が小さいものから大きいものへ、列要素が小さいものから大きいものへと増加する配列検索アルゴリズムを、関連する内容も含めて紹介しましたので、PHPチュートリアルに興味のある友人の参考になれば幸いです。