【剑指offer】二维数组中的查找

题目链接：https://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e?tpId=13&&tqId=11154&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
题目描述
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
示例1
输入

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

返回值

true

朴素算法：搜索整个二维数组，时间复杂度为O(N²)；

public class Solution {
    public boolean Find(int target, int [][] array) {
        int n=array.length;
        int m=array[0].length;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(array[i][j]==target){
                    return true;
                }
                /*if(array[i][j]>target){
                    break;//这也是一个改进办法，不过提升效率不高
                }*/
            }
        }
        return false;
    }
}

二分算法：因为每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。我们可以利用数组的这个特点对二维数组进行二分查找。
Java Code

public class Solution {
    public boolean Find(int target, int [][] array) {
        if(array==null){
            return false;
        }
        int n=array.length;
        int m=array[0].length;
        if(n<=0||m<=0){
            return false;
        }
        int i=0,j=m-1;//最开始选取右上角的数字
        while(i<n&&j>=0){//退出条件
            if(target==array[i][j]){
                return true;//找到则退出
            }
            else if(target>array[i][j]){
                i++;//target在第i行的下面
            }
            else{
                j--;//target在第j列的左边
            }
        }
        return false;//数组不存在target
    }
}

Cpp Code

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        int n=array.size();
        int m=array[0].size();
        if(n<=0||m<=0){
            return false;
        }
        int i=0,j=m-1;
         while(i<n&&j>=0){//退出条件
            if(target==array[i][j]){
                return true;//找到则退出
            }
            else if(target>array[i][j]){
                i++;//target在第i行的下面
            }
            else{
                j--;//target在第j列的左边
            }
        }
        return false;//数组不存在target
    }
};

【剑指offer】二维数组中的查找

推荐阅读