李明徽的算法|剑指Offer（面试题4-1）——二维数组中的查找李明徽的算法|面试题

剑指 Offer——面试题 4-1 题目在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
【李明徽的算法|剑指Offer（面试题4-1）——二维数组中的查找】请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
样例

输入数组：[ [1,2,8,9]， [2,4,9,12]， [4,7,10,13]， [6,8,11,15] ]如果输入查找数值为7，则返回true，如果输入查找数值为5，则返回false。

思路 ? 首先这道题如果使用暴力做法，遍历数组的每个元素来进行查找的话，时间复杂度为O(n2)，这显然不是一个精妙的解法，我们要通过一些特殊的性质，来减少我们需要访问的元素个数
? 怎么做呢，我们可以看到，整个二维数组是每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序，这是一条很重要的性质，也就是说，每一列的第一个元素是整列中最小的，每一行的第一个元素也是整行中最小的，我们可以从这个数组的右上角开始检测，如果右上角的元素大于target，我们就可以直接排除掉最右边的一列，因为target < 右上角元素 < 最右边的一列中其他元素，而如果右上角元素大于target，那么我们就可以删除最上边的一行，因为有target > 右上角元素 > 第一行中的其他元素，根据这个性质，我们可以每次去除二维数组的一行或者是一列，这样可以大大缩减我们查找所消耗的时间，下面看代码
代码

class Solution { public: bool searchArray(vector> array, int target) { if (array.size() == 0) return false; int i = 0; int j = array[0].size() - 1; while (i < array.size() && j >= 0) { if (array[i][j] == target) return true; if (array[i][j] > target) --j; if (array[i][j] < target) ++i; } return false; } };

class Solution { public boolean searchArray(int[][] array, int target) { if (array.length == 0) return false; for (int i = 0, j = array[0].length - 1; i < array.length && j >= 0; ) { if (array[i][j] == target) return true; if (array[i][j] > target) --j; else ++i; } return false; } }