学步园

剑指offer里面的题目。

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

对于下面这样的二维数组：

                                  1                       2                         8                             9

                                  2                       4                         9                            12

                                  4                       7                        10                           13

                                  6                       8                        11                           15

对于这样的二维数组，如果我们要查找7是否存在，我们该如何做呢？  我们使用两个指针一个行指针i，一个列指针j，i=0~row-1,j = column-1~0;

当7大于A[i][j]时，表明7大于A[i][j]所在的行，我们就认为我们要查找的数在A[i][j]的下方，我们就让行指针往下走，如果7等于A[i][j]，表示我们已经找到了，如果7小于A[i][j]，证明7小于A[i][j]所在的列，我们认为我们要查找的数在A[i][j]

package com.offer;

public class FindK {
	public static boolean find(int A[][], int l, int row, int column) {
		boolean flag = false;
		int i = 0, j, k;
		for (j = column - 1, i = 0; j >= 0 && i < row;) {
			if (l == A[i][j]) {
				flag = true;//当要查找的数等于A[i][j]时，表示查找结束。
				break;
			} else if (l < A[i][j]) {
				j--;//当要查找的数小于A[i][j]时，要查找的数在当前这个数的左边，因此列指针左移。
			} else {
				i++;//当要查找的数大于A[i][j]时，要查找的数在当前这个数的下边，因此行指针下移。
			}
		}

		return flag;
	}
	
	public static void main(String[] args) {
		int A[][] = { { 1, 2, 4, 8 }, { 2, 4, 9, 12 }, { 4, 7, 10, 13 },
				{ 6, 8, 11, 15 } };
		boolean flag = find(A, 5, 4, 4);
		System.out.println("flag:" + flag);
	}
}