1.题目描述：
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下的顺序排序。请完成一个函数，判断数组中是否包含指定的数字。
2.解题思路：
可以选择数组左下角的数字进行比较，因为如果要找的数字num比它小，则说明需要去它上边的一行去判断；如果要找的数字num比它大，则说明需要去它右边的一列去判断。事实上，也可以选择右上角的数字开始，但是不能选择左上角或者右下角，因为要保证所选数字的两条边一条在递增一条在递减，否则就不知道比较后该往哪里继续判断。
3.代码实现：
public class Offer_4 {
public static void main(String[] args) {
int[][] array = {
{1, 2, 8, 9},
{2, 4, 9, 2},
{4, 7, 10, 13},
{6, 8, 11, 15}
};
System.out.println(FindNum(array, 12));
}
private static boolean FindNum(int[][] array, int num) {
if (array == null) {
return false;
}
int x = array.length - 1;
int y = 0;
while (x >= 0 && y < array.length) {
if (num > array[x][y]) {
y++;
} else if (num < array[x][y]) {
x--;
} else {
return true;
}
}
return false;
}
}
复杂度分析：
- 时间复杂度：O(n)，对于大小为n x n的数组，最少时间是第一次就找到num；最大时间是num在所选的数字的对角位置，需要判断2n -1次，总的时间复杂度为O(n).
- 空间复杂度：O(1)，不需要额外开辟新的空间。
