前言

二维数组是数组的数组，它在内存中占据连续的空间。在内存中从上到下存储各行元素，在同一行中按照从左到右的顺序存储。因此访问二维数组中的元素时，我们可以根据行号和列号计算出相对于首地址的偏移量。

题目描述(二维数组中的查找)

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

解题思路

首先，题目的特殊性在于，无论哪一行哪一列都是递增有序的。因此，假如我们从二维数组的最右上角元素 m 开始查找。首先如果刚好找到，则返回，否则，如果待找元素 nm，则 n 一定不会出现在 m 元素所在的行，那么我们就可以剔除 m 所在的行。再接着，只要一直循环比较下去，直到找到或者找不到为止。
算法的另一个思路是：也可以选取从数组的左下角元素开始比较。

算法实现

复杂度分析

时间复杂度

考虑最复杂的情况，即从右上角开始，剔除 m 行，又剔除 n 列，没找到元素，那这样的时间复杂度达到 O(m+n)。

空间复杂度

操作在原数组上进行，空间复杂度为O(1)。

参考

<<剑指offer第二版>>