使用双二分查找分治、递归的方式进行
通过传入当前的两个方向的双指针进行遍历,得到当前的中间值(向下取整)坐标
用中间值坐标与target进行对比,然后如果是大于target
那么将会继续检测当前中间值的上半部分与左半部分,进行递归操作
直至最后找到对应的target则输出true、否则判断当前指针大小,没找到输出false。
因为当前递归将会不断进行,所以将会把这个递归函数作为if的判断条件,如果找到了那么就返回true,解决了递归的终止条件与输出返回值的问题
原有想法:
搜索完第一行,得到一个最接近target的中点
问题:
没能搜索完全部的列数组,造成遗漏
本题遇到主要的问题
1、二维数组取值出问题,行列索引出错
2、分治后所要检测的数组值不够明确
3、递归终止的判断条件写错
/** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * @param target int整型 * @param array int整型二维数组 * @return bool布尔型 */ export function Find(target: number, array: number[][]): boolean { // write code here //线性搜索 //通过搜索每一个对应的值 /* let i=array.length-1,j=0 if(array.length==0) return false while(i>=0 && j<array[0].length) { if(array[i][j] < target ) { j++ } else if(array[i][j]==target) { return true } else { i-- } } return false*/ //双重二分查找 if(array.length ==0 ) return false //return double_binary(array,0,array[0].length-1,0,array.length-1,target) return double_binary(array,0,array.length-1,0,array[0].length-1,target) } function double_binary(array: number[][],x1:number,x2:number,y1:number,y2:number,target:number):boolean { if(x1>x2 || y1> y2) return false let midx = Math.floor((x1+x2)/2) let midy = Math.floor((y2+y1)/2) if(array[midx][midy]==target) return true if(array[midx][midy] > target) { //中点上部 if(double_binary(array,x1,midx-1,y1,y2,target)) return true //中点左侧 if(double_binary(array,midx,x2,y1,midy-1,target)) return true } else { //中点右侧 if(double_binary(array,midx+1,x2,y1,y2,target)) return true //中点 if(double_binary(array,x1,midx,midy+1,y2,target)) return true } return false }