剑指offer题目训练3：二维数组中的查找

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。

请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

样例

输入数组：

[
  [1,2,8,9]，
  [2,4,9,12]，
  [4,7,10,13]，
  [6,8,11,15]
]

如果输入查找数值为7，则返回true，

如果输入查找数值为5，则返回false。

1. 思路，乍一看没什么好的思路就是遍历一遍O(n2)。仔细观察这个二维数组行和列是有序的，我们可以从右上角的数字开始，如果查找值比这个数字大，那么这一行就不用找了，只需从下一行的右上角继续开始找；如果查找值比这个数字小，那么这个数字所在列及右边的列就不用找了，只需从前一列的右上角继续找，这样就会节省很多搜索的时间，复杂度为线性时间。这道题用了类似二分的思路，一种变形。

2. 代码:

   
   

3. class Solution {
   public:
       bool searchArray(vector<vector<int>> array, int target) {
           //数组为空，返回false
           if(array.empty()||array[0].empty()) return false;
           //数组右上角位置开始
           int i=0,j=array[0].size()-1;
           //不越界没找到就继续搜索
           while(i<=array[0].size()-1&&j>=0){
               //找到了,返回true
               if(array[i][j]==target) return true;
               //右上角值比要找的数小,直接找下一行
               if(array[i][j]<target) i++;
               //右上角值比要找的数大,直接找上一列
               else j--;
           }
           return false;
       }
   };