Offer04（二维数组中的查找）

发表于 | 分类于 ，

题目：

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

思路：

　　此题很容易想到通过每行进行二分查找来解题，但此法时间复杂度较高。通过从右上角开始查找，如果该处数字大于要查找的数字，则可以排除该列，如果该处数字小于要
查找的数字，则可以排除该行，如果等于要查找的数字，则直接返回true。这种思路的时间复杂度明显高于通过每行进行二分法查找。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 public boolean Find1(int target, int [][] array) {
 	int row = 0;
 	int columns = array[0].length - 1;
 	while(row < array.length && columns >= 0) {
 		if (array[row][columns] == target) {
	return true;
}else if (array[row][columns] > target) {
	columns--;
}else {
	row++;
}
 	}
 	return false;
 }

复杂度分析及总结：

　　时间复杂度：
　　　　O(n)。
　　空间复杂度：
　　　　O(1)。