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

题目链接：https://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e?tpId=13&&tqId=11154&rp=1&ru=http://www.likecs.com/ta/coding-interviews&qru=http://www.likecs.com/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(N2)；

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 } };