大家好，又见面了，我是你们的朋友全栈君。
问题：在一个二维数组中，每行每列都递增排序，在这个数组中查找一个数字，如果存在返回true，否则返回flase。
分析：数组查找一直都是初学java的同学的热门考点，关于查找主要有顺序查找、二分查找、哈希表查找、二叉排序树查找。
我们看下下面这个数组，数组满足每行每列都是递增顺序。在这个数组中查找某个数，如果存在，返回true和所在位置。否则返回flase。
这里我们该选择什么样的方式来查找呢，首先排除顺序查找，顺序查找是大部分人都应该会的，这里不需要做太多介绍。
然后通过数组特性分析，一个排序好的数组，我们首先考虑二分法，如果数组中选取的数字和要查找的数字相等时，查找结束。如果选取的数字大于要查找的数字。那么根据数组要求，所查找数字位于选取数字的左边和上边（图）。反之就是在右边或下边（图2）
可以看到，这样方法中，由于要查找的数字相对于当前选取的位置有可能在两个区域中出现，而且这两个区域还有重叠的部分，这样问题看起来就复杂了，于是很多人卡住这里束手无策。为什么会遇到这种难题呢，是因为我们选取的数是二维数组中间的数字。如果我们从数组的一个角上来选取一个数会不会变得简单点呢？还是上图的例子。我们来看一下。首先我们选取数组右上角的9，有三种情况：
1）要查找的数等于9，查找结束。
2） 要查找的数字大于9，那么9所在的这一行就可以排除了，因为从这个数组的特征可以看到9就是这一行的最大数。最大数都小于要查找的数字，那这一行当然不可能等于要查找的数。所查找的数字在剩下的区域（图3）。
3）要查找的数小于9，那么9所在的这一列可以排除，因为9所在这一列中9是最小的数字。同理，查找的数字在剩下的区域（图4）。
通过上一步。我们可以得到一个新的4×3或者3×4的数组。对新的数组继续执行上述步骤。直到数组变为0x0。即表明数组中没有我们要查找的数字。以上就是我们的思路。具体代码实现如下：
package array;
public class FindInPartiallySortedMatrix {
private int row, col;
private boolean isFind;
public FindInPartiallySortedMatrix Find(int[][] a,int find){
int rows = a.length-1,cols = a[0].length-1,firstrows = 0;
if(rows<=0||cols<=0){
System.out.println("数组为空，无任何数据");
}
else{
isFind = false;
while (firstrows<=rows&&cols>=0){
if(a[firstrows][cols]>find){
--cols;
}
else if(a[firstrows][cols]<find){
++firstrows;
}
else {
this.row = firstrows;
this.col = cols;
this.isFind = true;
break;
}
}
}
System.out.println(this.isFind + " " + this.row + " " + this.col);
return this;
}
public static void main(String[] args){
int[][] a ={
{1,2,8,4},{2,4,9,12},{4,7,10,13},{6,8,11,15}};
FindInPartiallySortedMatrix finds = new FindInPartiallySortedMatrix();
finds.Find(a,1);
finds.Find(a,7);
finds.Find(a,13);
finds.Find(a,15);
finds.Find(a,3);
//System.out.println(finds.isFind+" "+finds.row+" "+finds.col);
}
}
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/138945.html原文链接：https://javaforall.net
