题目描述

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

样例

现有二维数组 array 如下：
[
  [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]
]
给定 target=5，返回true。

给定target=20，返回false。

算法1

(暴力枚举) $O(n^2)$

遍历每一个元素。

东拼西凑伪代码

 if(array == None or len(array) == 0)
 {
     return false;
 }

 for i in range(row)
 {
     for j in range(col)
     {
         if(array[i][j] == target)
         {
             return true;
         }
     }
 }
 else
 {
     return false;
 }

算法2

(二分查找) $O(nlogn)$

二分查找的复杂度为O(logn)，这里有n行，则为O(nlogn)。

因为二维数组的每一行都是按照从左到右递增的顺序排列的，所以可以遍历二维数组的每一行，然后每一行使用二分法进行查找。

东拼西凑伪代码

 if(array == None or len(array) == 0)
 {
     return false;
 }

 for i in range(row)://遍历行数
    start = 0;
    end = col - 1;//列数减一
    while start <= end:
        mid = start + (end - start)//2;
        if matrix[i][mid]>target:
            end = mid-1
            elif matrix[i][mid]<target:
                start = mid+1
            else:
                return True
    return False

算法3

（左下角标志数法） $O(1)$

从左下角开始遍历，如果当前值比target小则往上找，如果比target大则往右找，如果存在，必然可以找到目标数字。

真实cpp代码

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        if( array.size() == 0)
        {
            return false;
        }
        //行
        int row = 0; 
        //列
        int col = array[0].size() - 1;
        while( col >= 0 && row < array.size())
        {
            if(target == array[row][col])
                return true;
            else if(target < array[row][col])
                col--;
            else
                row++;
        }
        return false;
    }
};