4.二维数组中的查找

题目

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

Consider the following matrix:
[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

Given target = 5, return true.
Given target = 20, return false.

思路

取右上角或左下角数作为起点一一计较,向左走或向下走,直到找到位置
时间:O(M+N)

public class Findnum4 {
    public boolean Find(int target, int[][] array) {
        boolean flag = false;
        int a1 = 0;
        int a2 = array[0].length - 1;
        while (a1 < array.length && a2 >= 0) {
            if (target == array[a1][a2]) {
                flag = true;
                break;

            } else if (target < array[a1][a2]) {
                a2--;
            } else {
                a1++;
            }
        }
        return flag;
    }
}