二维数组中的查找

感觉已经有点晚了,赶紧刷起来,不过我喜欢这种感觉。。
下面主要是用于自己的学习记录,会有参考学习大牛的思路,毕竟我还是小白。。。。

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

题目解析:首先这个题不难,有几个思路可以参考

  • 思路1:可以暴力搜索,就是从第一行的第一个开始比较,然后遍历完所有的行和每行的所有数,但感觉这个很傻,就不试了。
  • 思路2: 可以采用二分查找法,这个也容易想到,每一行进行二分查找,因为题目已经给定行是有序递增的,列也是有序递增的。
  • 思路3: 矩阵是有序的,从左下角来看,向上数字递减,向右数字递增,因此从左下角开始查找,当要查找数字比左下角数字大时。右移要查找数字比左下角数字小时,上移。这样每一步比较都是最优的,利用数组的有序排序,避免了很多无用的比较。比如:
    [ 1 2 3 4 5 6 7 8 9 10 11 12 ] \begin{bmatrix} 1&2 &3 &4 \\ 5&6 &7 &8 \\ 9&10 &11 &12 \end{bmatrix} 159261037114812
    如果要查询的整数是7,这时从左下角开始比较,我们会发现比较的顺序依次是:9—>5—>6—>7,比较了4 次就找了目标值,可以看出刚才比较的过程中并没有和1,2,3,4,8,10,11,12比较。

思路二代码:
二分查找的条件是对一组有序数组的查找,这一点很容易忘记,在使用二分查找的时候先要对数组进行排序。

先说一下二分查找的思路:一个有序数组,想要查找一个数字key的下标,首先算出中间下标mid,利用mid把这个数组分为两半,前一半从下标0到mid-1,后一半从mid+1到数组最后一个元素(下标是数组长度减一)。把这个查找的元素key和数组下标为mid的元素进行比较,也就是和中间那个元素进行比较,如果比这个元素的小那么把查找范围缩小到原数组的前一半(把查找下标缩短到0到mid-1),如果比中间mid下标元素大那么范围就是后半部分(下标为mid+1到数组长度减一),这样来回反复取中间比较最后就会定位到要查找元素key的下标。

public class TwoDimArrayLookup{ 

	 public static void main(String[] args){ 
		 TwoDimArrayLookup mm=new TwoDimArrayLookup();
		 int a[][]={ { 1,2,3,4,5},{ 6,7,8,9,10},{ 11,12,13,14,15}};
		 boolean x=mm.Find(14,a);		
		 System.out.println("x:"+x);
		 System.out.println("a:"+a.length);
	 }
	
	 public boolean Find(int target,int [][] array) { 
		 for(int i=0;i<array.length;i++){ 
			 System.out.println("i:"+i);
			 int low =0;
			 int high=array[i].length-1;
			 while(low<=high){ 
				 int mid=(low+high)/2;
				 if (target<array[i][mid])
					 high=mid-1;				 
				 else if(target>array[i][mid])
					 low=mid+1;		
				 else 
					 return true;								
			 }			 
		 }		
		return false;
	 }	  
}		 

运行:

i:0
i:1
i:2
x:true
a:3

思路三代码:


public class TwoDimArrayLookup{ 

	 public static void main(String[] args){ 
		 TwoDimArrayLookup mm=new TwoDimArrayLookup();
		 int a[][]={ { 1,2,3,4},{ 5,6,7,8}};
		 boolean x=mm.Find(3,a);		
		 System.out.println("x:"+x);
		 System.out.println("a:"+a.length);
	 }
		 
	 public boolean Find(int target,int [][] array) { 
		 int len=array.length-1;
		 int i=0;
		 
		 while((len>=0)&&(i<array[0].length)){ 
		 if	 (array[len][i]==target){ 
			 return true;
		 	}
		 else if (array[len][i]<target)
			 	i++;			 		 	
		 else 
			 len--;
		 }
		 return false;
   }
}

    原文作者:lilong117194
    原文地址: https://blog.csdn.net/lilong117194/article/details/83722673
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞