剑指offer面试题3 二维数组中的查找

考察点：

	考察数据结构二维数组

知识点：

	1.java中的数据类型分为基本类型和引用类型，数组属于引用类型，引用类型的变量中存储的是地址，该地址指向内存中的某个对象，参考c中的指针。
	2.一维数组定义，初始化，遍历
	2.1.先定义后初始化：尤其注意如果只定义没有初始化那么元素会被初始化为数据类型的默认值，int会被初始化为0，float会被初始化为0.0，boolean会被初始化为false
	int arr[] = new int[2];
	arr[0] = 10;
	2.2.定义的时候同时初始化：
	int arr[] = {1,2};
	int arr[] = new int[] {1,2};
	2.3.数组遍历
	2.3.1.for (int i = 0;i < arr.length;i++) {
			System.out.println(arr[i]);
		}
	2.3.2.for (int a : arr) {
		System.out.println(a);
	}
	2.3.3.java标准库
	System.out.println(Arrays.toString(arr));
	3.二维数组定义，初始化，遍历
	3.1.先定义后初始化
	int arr[][] = new int[2][3];
	int brr[] = new int[3];
	int crr[] = new int[3];
	arr[0] = brr;
	arr[1] = crr;
	注意此时arr.length = 2,而arr[0].length = 0,arr[1].length = 0;
	3.2.定义的时候同时初始化
	int arr[][] = {
		{1,2,3},
		{4,5,6},
		{7,8,9}
	}
	3.3.数组的遍历
	3.3.1 for (int i = 0;i < arr.length; i++) {
			for (int j = 0;j<arr[0].length;j++) {
				System.out.println(arr[i][j]);
			}
		}
	3.3.2.for (int brr[] : arr) {
			for (int n : brr) {
				System.out,println(n);
			}
		}

题目：

分析：
关于数组这个数据结构的考点无非就是数组遍历。本题目要求判断一个二维数组中是否含有某一个数字，直接遍历二维数组也可以满足需求，但此种解法复杂度为O(n^2)，题目不会这么简单，那延伸一下考察的点无非就是如何提升遍历的效率，试想一下每次二维数组一个循环只能遍历掉一个元素，如果一个循环遍历掉一块元素的话，那效率就会极大的提升。仔细观察题目，其中设定了数组的一些属性，那么这些属性的目的大概率就是冲着减少遍历元素的目的去的。每行每列都是递增排序，试想如果一行(或者一列)中最大的那个元素比待查找的元素小，那这个待查找的值肯定不会出现在这个最大元素所在的行(或者列)；如果一行(或者一列)中最小的那个元素比待查找的元素大，那么这个待查找的值也肯定不会出现在这个最小元素所在的行(或者列)。而题目中的这个二维数组中左上角和右下角的元素就满足这样的特性，因为左上角元素是行的最大值列的最小值，右下角是行的最小值列的最大值，拿左上角举例，如果该元素比待查找的元素小，那么这个元素所在的行就可以不用遍历了，如果该元素比待查找的元素大，那么这个元素所在的列就可以不用遍历了。
代码：

public class Three {
	public static void main(String [] args) {
		int arr[][] = {
			{1,2,8,9},
			{2,4,9,12},
			{4,7,10,13},
			{6,8,11,15}
		};
		System.out.println(find(arr,arr.length,arr[0].length,7));
		System.out.println(find(arr,arr.length,arr[0].length,71));
		int brr[][] = new int[0][0];
		System.out.println(find(brr,brr.length,0,71));
		int crr[][] = new int[1][0];
		crr[0] = new int[0];
		System.out.println(find(crr,crr.length,crr[0].length,71));
	}
	public static boolean find(int [][] arr,int rows,int cols,int val) {
		if (null == arr || arr.length == 0
			|| (arr.length == 1 && arr[0].length == 0)
			|| rows <=0 || cols <= 0) {
			return false;
		}
		int row = 0;
		int col = cols - 1;
		while (row < rows && col >=0) {
			if (arr[row][col] == val) {
				return true;
			}
			if (arr[row][col] < val) {
				row ++;
			} else {
				col --;
			}
		}
		return false;
	}
}