二维数组中的查找JZ1
二维数组中的查找
http://www.nowcoder.com/questionTerminal/abc3fe2ce8e146608e868a70efebf62e
在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
输入示例:7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
输出示例:true
我的解决方案:
方法一:暴力求解
直接两个for循环方法二:折半查找
如图蓝***域可以看成一个有序的序列,直接对这个有序序列进行折半查找即可。
可以看出这个二维数组一共有4个这样的有序序列,也就是二维数组的最低维度,当把最外侧的有序序列查找完毕之后,就需要转到内部的有序序列,经过分析可以知道,每次跳转到内部有序序列的时候,序列长度-2。这样以来只需要再计算出mid的横纵坐标,就可以直接使用折半查找了。public class JZ1 { public boolean Find(int target, int [][] array) { if(array==null){ return false; } int num_length=array.length+array[0].length-1;//初始化二分查找的数组长度 for(int i=0;i<Math.min(array.length, array[0].length);i++){//总共执行二分查找的外部循环次数 int low=0; int mid; int high=num_length-1; while (low<=high){ mid=(low+high)/2; int row_index,column_index;//定位mid的位置 if(mid>array[i].length-i-1){ //说明mid在序列的右侧列上 row_index=mid-(array[i].length-1-i)+i; column_index=array[0].length-1-i; }else { //说明mid在序列的左侧行上 row_index=i; column_index=mid; } //进行折半 if(target>array[row_index][column_index]){ low=mid+1; }else if(target<array[row_index][column_index]){ high=mid-1; }else if(target==array[row_index][column_index]){ return true; } } num_length=num_length-2;//每次查找完毕,有序序列长度-2 } return false; } public static void main(String args[]){ int [][]a={{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15},{14,16,17,18},{20,21,22,23},{24,25,26,27}}; JZ1 jz1=new JZ1(); System.out.println(jz1.Find(1,a)); } }