剑指 Offer 04. 二维数组中的查找

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof
 

方法一：(空间占用小，耗时)

根据矩阵元素的特点：从左到右，从上到下递增，利用右上角元素缩小查找范围，

        若查找元素=右上角元素，查找结束；

        若查找元素<右上角元素，则该元素若存在，一定在右上角元素的左侧的各列中；

        若查找元素>右上角元素，则该元素若存在，一定在右上角元素的下侧的各行中。

bool findNumberIn2DArray(vector>& matrix, int target) {
    int n,m,row,col;
    bool res = false;
    if(matrix.size()<1 || matrix[0].size()<1){
        return false;
    }
    n = matrix.size();
    m = matrix[0].size();
    row = 0; col = m-1;
    while(row= 0){
        if(matrix[row][col] == target){
            return true;
        }else if(matrix[row][col] > target){
            col--;
        }else{
            row++;
        }
    }
    return res;

}

方法二：（空间大，稍快）

利用矩阵的主对角线元素，首先寻找矩阵中方阵元素的主对角线第一个比查找元素大的位置：

        若没找到（下标到达矩阵中的方阵的行列个数）

        （1）矩阵是方阵，则不在其中，返回false

        （2）若矩阵的行数n<列数m，则元素在方阵右侧区域，根据右上角元素限定查找范围

        （3）若矩阵的行数n>列数m，则元素在方阵下侧区域，根据左下角角元素限定查找范围

        若找到了（查找元素在矩阵的方阵的右侧或者下侧）

        （1）主对角线元素就是查找元素，返回true

        （2）在当前位置右侧

        （3）在当前位置下侧

代码如下：

bool findNumberIn2DArray(vector>& matrix, int target) {
    
    int n,m,min_size,j,k,i=0;
    int search_row,search_col;
    bool res;
    if(matrix.size()<1 || matrix[0].size()<1){
        return false;
    }
    n = matrix.size();
    m = matrix[0].size();
    min_size = n>m?m:n;
    while(i