题解 | #二维数组中的查找#
https://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e
使用双二分查找分治、递归的方式进行
通过传入当前的两个方向的双指针进行遍历，得到当前的中间值（向下取整）坐标
用中间值坐标与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
}
投递快手等公司7个岗位
