二维数组中的查找

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

例如：下面的二位数组都是每行梅列递增，如果在这个数组中查找数字7，如果有就返回true，如果没有就返回fasle。

    1   2   8    9

     2  4   9   10

     4  7  10  13

     6  8  11   15

思路：1.选取数组的右上角的数字比较，9比7大，那么9这一列中9最小都没有比7小那么，在这一列中没有比7小的了。那么这一行可以不考虑了，剔除掉9所在这一列（图a）。看剩下的，最右上角，那么就是不8，同理剔除8所在的这一列（图b），剩下的就是这个右上角是2，明显比7小，那么在剔除完，其余的后，发现，第一列中2最大，最大的数没有7大，那么这一行也可以剔除（图c）第二行，此时，数组中只剩下了四个数字，依旧是最右上角的数字，刚好是7，就一比较结束（图d）。 

总结一下，那就是每次拿右上角的数字和要查找得数字比较，大于则剔除列，小于则剔除行。实现这么一个函数就可以了。当然也可以从左下角开始查找，道理一样。

java代码如下：

package com.cb.java.algorithms.jianzhioffer;

/**
 * 在二维数组中查找数字
 * 
 * @author
 *
 */
public class FindNumberInTwoDimensionArray {

	/**
	 * 从右上角开始查找
	 * 
	 * @param arr
	 * @param num
	 * @return
	 */
	public static boolean findFromRightUp(int[][] arr, int num) {
		int row = 0;
		int col = arr[0].length - 1;
		while (row <= arr.length - 1 && col >= 0) {
			if (arr[row][col] == num) {
				System.out.println("第" + (row + 1) + "行" + (col + 1) + "列");
				return true;
			} else if (arr[row][col] > num) {
				--col;
			} else {
				++row;
			}

		}
		return false;
	}

	/**
	 * 从左下角开始查找
	 * 
	 * @param arr
	 * @param num
	 * @return
	 */
	public static boolean findFromLeftDown(int[][] arr, int num) {
		int row = arr[0].length - 1;
		int col = 0;
		while (col <= arr.length - 1 && row >= 0) {
			if (arr[row][col] == num) {
				System.out.println("第" + (row + 1) + "行" + (col + 1) + "列");
				return true;
			} else if (arr[row][col] > num) {
				--row;
			} else {
				++col;
			}

		}
		return false;
	}

	public static void main(String[] args) {
		int[][] arr = { { 1, 2, 8, 9 }, { 2, 4, 9, 12 }, { 4, 7, 10, 13 }, { 6, 8, 11, 15 } };
		findFromRightUp(arr, 7);
		findFromLeftDown(arr, 9);
	}
}

在上述查找过程中，可以从左下角或者右上角开始查找，但不能从左上角或者右下角开始查找。以左上角数字为例，最初数字为1，由于1小于7，那么7应该位于1得右边或者下边。此时不能从查找范围内剔除1所在的行，也不能剔除1所在的列，无法缩小查找范围。

参考：

[1]《剑指Offer》

[2]https://blog.csdn.net/qq_35256722/article/details/53691946